Xuedong Shang

Emilie Kaufmann

Michal Valko
email: michal.valko@

Aurélien Garivier

Satyen Kale

General parallel optimization without a metric

Keywords: continuously-armed bandits, global optimization, black-box optimization

Hierarchical bandits are an approach for global optimization of extremely irregular functions. This paper provides new elements regarding POO, an adaptive meta-algorithm that does not require the knowledge of local smoothness of the target function. We first highlight the fact that the subroutine algorithm used in POO should have a small regret under the assumption of local smoothness with respect to the chosen partitioning, which is unknown if it is satisfied by the standard subroutine HOO. In this work, we establish such regret guarantee for HCT, which is another hierarchical optimistic optimization algorithm that needs to know the smoothness. This confirms the validity of POO. We show that POO can be used with HCT as a subroutine with a regret upper bound that matches the one of best-known algorithms using the knowledge of smoothness up to a √ log n factor. On top of that, we propose a general wrapper, called GPO, that can cope with algorithms that only have simple regret guarantees. Finally, we complement our findings with experiments on difficult functions.

Introduction

Global optimization (GO) has applications in several domains including hyper-parameter tuning [START_REF] Jamieson | Non-stochastic best arm identification and hyperparameter optimization[END_REF][START_REF] Li | Hyperband: Bandit-based configuration evaluation for hyperparameter optimization[END_REF][START_REF] Samothrakis | Training gradient boosting machines using curve-fitting and information-theoretic features for causal direction detection[END_REF]. GO usually consists of a data-driven optimization process over an expensive-to-evaluate function. It is also known as black-box optimization since the inner behavior of a function is often unknown.

In GO, we optimize an unknown and costly-to-evaluate function f : X → R based on n noisy evaluations, that can be sequentially selected. This setting is a generalization of multi-armed bandits, where the arm space X is some measurable space [START_REF] Bubeck | X-armed bandits[END_REF]. Each arm x ∈ X gets its mean reward f (x) through the reward function f , which is the function to be optimized. At each round t, the learner chooses an arm x t ∈ X and receives a reward r t . We study the noisy setting in which the obtained reward is a noisy evaluation of f : r t f (x t ) + ε t , where ε t is a bounded noise.

Treating the setting without any further assumption would be a mission impossible. However, the setting gets easier if we assume a global smoothness of the reward function [START_REF] Agrawal | The continuum-armed bandit problem[END_REF] c 2019 X. Shang, E. Kaufmann & M. Valko. [START_REF] Robert | Nearly tight bounds for the continuum-armed bandit problem[END_REF][START_REF] Kleinberg | Multi-armed bandit problems in metric spaces[END_REF][START_REF] Cope | Regret and convergence bounds for immediate-reward reinforcement learning with continuous action spaces[END_REF][START_REF] Auer | Improved rates for the stochastic continuumarmed bandit problem[END_REF][START_REF] Slivkins | Multi-armed bandits on implicit metric spaces[END_REF][START_REF] Kleinberg | Bandits and experts in metric spaces[END_REF]. A weaker condition is some local smoothness where only neighborhoods around the maximum are required to be smooth. In fact, local smoothness is sufficient for achieving nearoptimality [START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF][START_REF] Gheshlaghi Azar | Online stochastic optimization under correlated bandit feedback[END_REF][START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF][START_REF] Bull | Adaptive-treed bandits[END_REF]. We base our work on optimistic tree-based optimization algorithms [START_REF] Munos | Optimistic optimization of deterministic functions without the knowledge of its smoothness[END_REF][START_REF] Valko | Stochastic simultaneous optimistic optimization[END_REF][START_REF] Preux | Bandits attack function optimization[END_REF][START_REF] Gheshlaghi Azar | Online stochastic optimization under correlated bandit feedback[END_REF] that approach the problem with a hierarchical partitioning of the arm space and take the optimistic principle. This idea comes from planning in Markov decision processes [START_REF] Kocsis | Bandit-based Monte-Carlo planning[END_REF][START_REF] Munos | From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning[END_REF][START_REF] Grill | Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning[END_REF].

Our work is motivated by the parallel optimistic optimization (POO) approach proposed by [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF], that adapts to the smoothness without the knowledge of it. POO is a meta-algorithm which can be used on top of any hierarchical optimization algorithm that knows the smoothness, that we call a subroutine. Not only does POO require only the mildest local regularity conditions, but it also gets rid of the unnecessary metric assumption that is often required. Local smoothness naturally covers a larger class of functions than global smoothness, yet still assures that the function does not decrease too fast around the maximum. We highlight that the analysis of POO is modular: Assuming the subroutine has a regret of order R n under a local smoothness assumption with respect to a fixed partitioning [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF], Assumption 1, formally introduced in Section 2), POO run with such subroutine has a regret bounded by R n √ log n. POO was originally analyzed using HOO as a subroutine. However, unlike what [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] hypothesize, it is non-trivial to provide a regret bound for HOO under Assumption 1. We elaborate on that in Section 3. In order to validate POO, there needs to exist a subroutine with a regret guarantee that is provable under Assumption 1. This is what we deliver.

In particular, we prove that HCT-iid 1 of [START_REF] Gheshlaghi Azar | Online stochastic optimization under correlated bandit feedback[END_REF] satisfies the required regret guarantee, and is, therefore, a desirable subroutine to be plugged in POO. Similar to HOO, HCT is a hierarchical optimization algorithm based on confidence intervals. However, unlike HOO, these confidence intervals are obtained by repeatedly sampling a representative point of each cell in the partitioning before splitting the cell. This yields partition trees that have a controlled depth, which are easier to analyze under a local smoothness assumption with respect to the partitioning. Whether HOO has similar regret guarantees under the desired local metricless assumption remains an open question.

POO requires the subroutine to have a cumulative regret guarantee. In this paper, we also provide a more general wrapper for algorithms that only have guarantee for their simple regret, called GPO (for general parallel optimization). We show that with a cross-validation scheme instead of the original recommendation strategy, any hierarchical bandit algorithm with simple regret guarantee can be plugged into GPO with only a tiny increase in the resulting simple regret.

Paper outline

We first formulate the sequential optimization problem and introduce some preliminary notions and assumptions in Section 2. Our main result is presented in Section 3, where we provide a regret upper bound for HCT under local smoothness with respect to the partitioning. In Section 4, we present the instantiation of POO studied in the paper that we call PCT, in which the underlying subroutine HOO is replaced by HCT. We show that PCT enjoys the same regret bound as HCT up to a √ log n factor. The general wrapper and its simple regret analysis are presented in Section 5. We conclude by some numerical simulations in Section 6.

Smoothness assumptions for black-box optimization

Let X be a measurable space. Our goal is to find the maximum of an unknown noisy function f : X → R of which the cost of evaluation is high, given a total budget of n evaluations. At each round t, a learner selects a point x t ∈ X and observes a reward r t f (x t ) + ε t , bounded by [0, 1], from the environment where the noise ε t is assumed to be independent from previous observations and such that E[ε t |x t ] = 0. After n evaluations, the algorithm outputs a guess for the maximizer, denoted by x(n). We assume that there exists at least one x ∈ X s.t. f (x ) sup x∈X f (x), denoted by f in the following. We measure the performance by the simple regret, also called the optimization error,

S n f -f (x(n)).
Another related notion is the cumulative regret, defined as

R n nf - n t=1 f (x t ).
As observed by [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF], a good cumulative regret naturally implies a good simple regret: If we recommend x(n) according to the distribution of previous plays, we immediately get

E[S n ] = E[R n ]/n.

Covering tree that guides the optimization

Hierarchical bandits rely on the existence of hierarchical partitioning P {P h,i } h,i defined recursively, where

P 0,1 = X , P h,i = K-1 j=0 P h+1,Ki-j .
Such a partition can be naturally represented by a tree, where K denotes the maximum number of children of a node in that tree. Many of known algorithms depend on a metric/dissimilarity over the search space to define the regularity assumptions that link the partitioning to some near-optimality dimension, that is independent of the partitioning. However, this was shown to be artificial [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF], since (i) the metric is not fully exploited by the algorithms and (ii) the notion of near-optimality dimension independent of partitioning is ill-defined. Hence, it is natural to make smoothness assumptions directly related only to the partitioning. We now present the only regularity assumption on the target function f that is expressed in terms of the partitioning P. We stress again that requiring only local smoothness assumptions is an improvement since (i) it covers a larger class of functions, (ii) it only constrains f along the optimal path of the covering tree which is a plausible property in an optimization scenario, and (iii) shows that the optimization is actually easier than it was previously believed.

Assumption 1 (local smoothness w.r.t. P) For x be a global maximizer, we denote by i h be the index of the only cell at depth h that contains x . Then, there exist a global maximizer x and two constants ν > 0, ρ ∈ (0, 1) s.t.,

∀h ≥ 0, ∀x ∈ P h,i h , f (x) ≥ f -νρ h .
Note that this assumption is the same as the one of [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF]. Multiple maximizers may exist, but this assumption needs to be satisfied only by one of them.

As first observed by [START_REF] Auer | Improved rates for the stochastic continuumarmed bandit problem[END_REF], the difficulty of a GO should depend on the size of near-optimal regions and on how fast they shrink. [START_REF] Auer | Improved rates for the stochastic continuumarmed bandit problem[END_REF] use a margin condition that quantifies this difficulty by the volume of near-optimal regions. In this work, we use a similar notion of near-optimality dimension instead. This notion is directly related to the partitioning.

Definition 1 (near-optimality dimension w.r.t. P) For any ν > 0, C > 1, and ρ ∈ (0, 1), we define the near-optimality dimension of f with respect to P as

d(ν, C, ρ) inf d ∈ R + : ∀h ≥ 0, N h (3νρ h ) ≤ Cρ -d h , 2
where N h (ε) is the number of cells P h,i such that sup x∈P h,i f (x) ≥ fε.

N h (3νρ h ) can be thought as the number of cells that any algorithm needs to sample in order to find the maximum. A smaller d(ν, C, ρ) implies an easier optimization problem.

HCT under local smoothness with respect to P

Analyzing HOO under Assumption 1 is not trivial. A key lemma in the analysis of HOO (Lemma 3 by [START_REF] Bubeck | X-armed bandits[END_REF]) that controls the variance of near-optimal cells is not true under local smoothness assumptions as Assumption 1. Indeed, HOO could induce a very deep covering tree, while producing too many nodes that are neither near-optimal nor sub-optimal. The concept of near-optimal and sub-optimal nodes is then characterized by the sub-optimality gap of each node which measures the distance between the local maximum of the node and the global maximum. Intuitively, nodes that are neither near-optimal nor sub-optimal represent the nodes of whom the sub-optimality gap is neither too large nor too small. To control the regret due to these nodes, [START_REF] Bubeck | X-armed bandits[END_REF] use global smoothness (weakly Lipschitz) assumption. Assumption 1 is weaker, only local, and does not offer such comfort. If we want to control the regret due to these nodes without Lemma 3 of [START_REF] Bubeck | X-armed bandits[END_REF], one possible way is to control the depth of the covering tree to ensure that we do not have too many of them. In particular, another algorithm known as HCT (Azar et al., 2014) implies a controlled depth of the tree which allows it to be analyzed under Assumption 1 as opposed to HOO. We now give a brief description of HCT and present a new analysis of it.

Description of HCT

The pseudocode of HCT (Algorithm 1) and two detailed snippets (Algorithm 2 and Algorithm 3) describe the process of traversing the covering tree. The algorithm stores a finite subtree T t at each round t which is initialized by T 0 = {(0, 1)}. Each cell is associated with a representative point x h,i and the algorithm keeps track of some statistics regarding this point. One of these statistics is the empirical mean reward µ h,i (t) which is the average on the first T h,i (t) rewards received when querying x h,i . The HCT algorithm also keeps track of an upper confidence bound U -value for the cell (h, i),

U h,i (t) µ h,i (t) + νρ h + c log(1/ δ(t + )) T h,i (t)
, Algorithm 1: High confidence tree (HCT, Azar et al. 2014)

Input : K, ν > 0, ρ ∈ (0, 1), c > 0, tree partitioning {P h,i }, confidence δ Initialize: T 1 ← {(0, 1), (1, 1), . . . , (1, K)}, U 1,1 (1) ← • • • ← U 1,K (1) ← +∞ 1 for t ← 1 to n do 2 if t = t + then 3 for (h, i) ∈ T t do 4 U h,i (t) ← µ h,i (t) + νρ h + c log(1/ δ(t + )) T h,i (t) 5 end 6 UpdateBackward(T t , t) 7 end 8 (h t , i t ), P t ← OptTraverse(T t , t) 9
Evaluate x ht,it and obtain r t

T ht,it (t) ← T ht,it (t) + 1 Update µ ht,it (t) U ht,it (t) ← µ ht,it (t) + νρ ht + c log(1/ δ(t + )) T h t ,i t (t) UpdateBackward(P t , t) τ ht (t) ← c 2 log(1/ δ(t + )) ν 2 ρ -2ht if T ht,it (t) ≥ τ ht (t) and (h t , i t ) is a leaf then Expand((h t , i t )) end end Algorithm 2: OptTraverse Input : a tree T , round t Initialize: (h, i) ← (0, 1); P ← {(0, 1)}; T 0,1 (t) = τ 0 (t) = 1 1 while (h, i) is not a leaf of T and T h,i (t) ≥ τ h (t) do 2 j ← arg max j∈{0,...,K-1} {B h+1,Ki-j (t)} 3 (h, i) ← (h + 1, Ki -j) 4 P ← P ∪ {(h, i)} 5 end 6 return (h, i) and P where t + 2 log 2 (t) , δ(t) min{c 1 δ/t, 1/2}, and its corresponding B-value, B h,i (t)    min U h,i (t), max j∈{0,...,K-1} {B h+1,Ki-j (t)} if (h, i) is an internal node, U h,i (t) otherwise,
Algorithm 3: UpdateBackward Input : a tree T , round t note that P t can also be considered as a tree, thus input of this function

1 for (h, i) ∈ T backward from each leaf of T do 2 if (h, i) is a leaf of T then 3 B h,i (t) ← U h,i (t) 4 else 5 B h,i (t) ← min U h,i (t), max j∈{0,...,K-1} {B h+1,Ki-j (t)} 6 end 7 end
which is designed to be a tighter upper confidence bound than the U -value. Here, c and c 1 are two constants, and νρ h represents the resolution3 of the region P h,i . Observe that U h,i (t) and B h,i (t)

are not updated at every round, but are constant on time intervals of the form [2 k , 2 k+1 ).

At each round t, the algorithm traverses the current covering tree along an optimistic path P t before choosing a point (OptTraverse function). This optimistic path P t is obtained by repeatedly selecting cells that have a larger B-value until a leaf or a node that is sampled less than a certain number of times is reached. If a leaf is reached, then this leaf is sampled and expanded (i.e., we split the leaf into K equal-sized regions and initialize their U -values to +∞); otherwise, the node that is not sampled enough is re-sampled. All the B-values along the optimistic path are then updated backwardly from the current node to the root (UpdateBackward function). More precisely, HCT samples one node a certain number of times τ h (t) in order to sufficiently reduce the uncertainty before expanding it. Hence, τ h (t) is defined such that the uncertainty over the rewards in P h,i is roughly equal to the resolution of the node,

τ h (t) c 2 log(1/ δ(t + )) ν 2 ρ -2h .

Analysis of HCT under a local metricless assumption

We now state our main theorem. We prove that HCT achieves an expected regret bound under Assumption 1 which matches the regret bound given by Azar et al. ( 2014) up to constants. Moreover, compared to that result, the near-optimality dimension d featured in Theorem 2 is the one of Definition 1 that is defined with respect to the partitioning and not with respect to a metric. For a fixed budget n, we introduce the notation HCT(ν, ρ) to refer to the instantiation of HCT parameterized by ν, ρ, c = 2 1/(1ρ) and δ = 1/n.

Theorem 2 Assume that function f satisfies Assumption 1. Then, setting δ 1/n, the cumulative regret of HCT(ν, ρ) after n function evaluations is upper bounded as

E[R HCT(ν,ρ) n ] ≤ αC(log n) 1/(d(ν,C,ρ)+2) n (d(ν,C,ρ)+1)/(d(ν,C,ρ)+2) ,
where α is a numerical constant and C is the constant associated to d(ν, C, ρ).

As a consequence, by simply applying the recommendation strategy that follows the distribution of previous plays, we get the following simple-regret bound.

Corollary 3 The simple regret of HCT after n function evaluations under Assumption 1 satisfies

E[S HCT(ν,ρ) n ] ≤ αC(log n) 1/(d(ν,C,ρ)+2) n -1/(d(ν,C,ρ)+2) .
We now sketch the proof. The full proof follows the analysis of Azar et al. ( 2014) and is detailed in Appendix A. As mentioned above, HCT has a controlled depth. Indeed, given the threshold τ h (t) required at depth h, in Section A.2, we prove that the depth of the covering tree is bounded as stated in the following lemma.

Lemma 4 The depth of the covering tree produced by HCT after n function evaluations satisfies

H(n) ≤ H max (n) 1 2(1 -ρ) log nν 2 c 2 ρ 2 •
Defining the mean reward µ h,i f (x h,i ), we introduce a favorable event under which the mean reward of all expanded nodes is within a confidence interval,

ξ t ∀(h, i) ∈ L t , | µ h,i (t) -µ h,i | ≤ c log(1/ δ(t))/T h,i (t) ,
where L t is the set of all possible nodes in trees of maximum depth H max (t).

We split the regret into two parts depending on whether ξ t holds or not. In Appendix A.4, we prove that the failing confidence term is with high probability bounded by √ n. In the case when ξ t holds, we bound the regret in Appendix A.5 by treating separately the two parts, ∆ ht,it and ∆ t , of the instantaneous regret ∆ t ,

∆ t f -r t = f -f (x ht,it ) + f (x ht,it ) -r t = ∆ ht,it + ∆ t .
Next, we bound ∆ t by Azuma-Hoeffding concentration inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF]. Then, we bound ∆ ht,it with the help of the following lemma, which is the major difference compared to the original HCT analysis by [START_REF] Gheshlaghi Azar | Online stochastic optimization under correlated bandit feedback[END_REF]. In particular, the lemma states that if Assumption 1 is verified then f is upper-bounded by the U -value of any optimal node. Lemma 5 Under Assumption 1 and under event ξ t , we have that for any optimal node (h , i ), U h ,i (t) is an upper bound on f .

Proof Since t + ≥ t, we have U h ,i (t) µ h ,i (t) + νρ h + c log(1/ δ(t + )) T h ,i (t) ≥ µ h ,i (t) + νρ h + c log(1/ δ(t)) T h ,i (t) •
Moreover, as we are under event ξ t , we also have

µ h ,i (t) + c log(1/ δ(t)) T h ,i (t) ≥ f (x h ,i ). Therefore, U h ,i (t) ≥ f (x h ,i ) + νρ h ≥ f .
With the help of Lemma 5 (see Step 2 in Appendix A.5), we can then upper bound ∆ ht,it as

∆ ht,it ≤ 3c log(2/ δ(t)) T ht,it (t) •
To bound the total regret of the all nodes selected, we divide them into two categories, depending on whether their depth is smaller or equal than H (to be optimized later) or not.

For the nodes in depths h ≤ H, we use Lemma 5 again, now to show that OptTraverse only selects nodes that have a parent which is (3νρ ht-1 )-optimal. For the nodes for which h > H, we bound the regret using the selection rule of HCT.

The sums of the regrets from the two categories are proportional and inversely proportional to an increasing function of H. By finding the value of H for which the sum of the two terms reaches its minimum and adding the regret coming from the situations where the favorable event does not hold, gives us the following cumulative regret for HCT:

With probability 1 -δ, R HCT(ν,ρ) n ≤ O (log(n/δ)) 1/(d(ν,C,ρ)+2) n (d(ν,C,ρ)+1)/(d(ν,C,ρ)+2) .
However, the analysis of POO requires a bound on the expected regret of the underlying subroutine. For that purpose, we simply set δ 1/n and that gives us the statement of Theorem 2, and consequently Corollary 3.

PCT that does not need to know the smoothness

In this section, we formally introduce a generic POO(A) algorithm, taking as input any algorithm A = A(ν, ρ) requiring the smoothness parameters. We provide a simple regret upper bound for a particular instantiation called PCT, for POO(HCT).

Generic parallel optimistic optimization

POO(A) (parallel optimistic optimization) is a meta-algorithm that uses any hierarchical optimization algorithm A that knows the smoothness as a subroutine, originally proposed by [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] for A = HOO. In this algorithm, several instances of A are run in parallel, each one using a different pair of parameters (ν, ρ) in a well-chosen grid G (defined in Line 4 of Algorithm 4). In the end, POO(A) chooses the instance that has the largest empirical mean reward and returns one of the points evaluated by this instance, chosen uniformly at random.

The pseudocode of POO(A) is shown in Algorithm 4. Additionally to the base algorithm itself, it requires two parameters ρ max and ν max that determine the range of A(ν, ρ) instances that we can compete with. However, these parameters can be set as a function of the number of evaluations as explained in details in Appendix C of [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF], hence not mandatory in practice. An important remark is that given a budget n of function evaluations, the number of A instances N run by POO(A) depends on n, and each instance is run for n/N (n) times. Due to the doubling scheme used in Lines 2-10, note however that POO(A) does not need to know this total number of function evaluations. Hence, if the base algorithm A is anytime, so is POO(A).

Upper bound on the simple regret of PCT

Building on our new analysis of the HCT algorithm, we are able to provide theoretical guarantees for the resulting POO(HCT) algorithm, that we refer to as PCT (parallel confidence tree). More precisely we define PCT(δ) as POO run on top of HCT using confidence parameter δ.

Letting (ν , C , ρ ) be a triple of parameters for which Assumption 1 is true, we prove that PCT achieves a regret that is comparable to the one obtained by c.

Theorem 6 Assume that the target function f satisfies Assumption 1 and ν ≤ ν max and ρ ≤ ρ max . For δ = N (n)/n with N (n) = (1/2)D max log(n/ log n) , the simple regret of PCT(δ) after n function evaluations is bounded as

E[S PCT(δ) n ] ≤ βD max (ν max /ν ) Dmax ((log 2 n)/n) 1/(d(ν ,C ,ρ )+2) ,
where β is a constant independent of ν max and ρ max . 4By Corollary 3, we know that the simple regret of HCT after n function evaluations run with (ν , C , ρ ) is of order O (log n/n) 1/(d(ν ,C ,ρ )+2) . As a consequence, the performance of PCT is at most a √ log n factor away from that of the best HCT instance. Theorem 6 follows from Corollary 3 and Proposition 7 below. This wrapper result highlights how cumulative regret guarantees for any base algorithm translate into simple regret guarantees for the corresponding POO(A) algorithm. Its proof almost replicates the analysis of POO(HOO) by [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] and we provide it in Appendix B for the sake of completeness.

Proposition 7 If for all (ν, ρ) the A(ν, ρ) algorithm has its cumulative regret bounded as

E R A(ν,ρ) n ≤ αC(log n) 1/(d(ν,C,ρ)+2) n (d(ν,C,ρ)+1)/(c+2) , (1)
for any function f satisfying Assumption 1 with parameters (ν, C, ρ), then there exists a constant β that is independent of ν max and ρ max such that

E S POO(A) n ≤ βD max (ν max /ν ) Dmax (log 2 n)/n) 1/(d(ν ,C ,ρ )+2) ,
for any function f satisfying Assumption 1 with parameters ν ≤ ν max and ρ ≤ ρ max .

General parallel optimization

The analysis of POO(A) proposed in Proposition 7 heavily relies on the fact that we control the cumulative regret of algorithm A. POO indeed exploits this property when selecting s as the instance with largest empirical cumulative rewards. In this section, we propose a simple modification of POO(A) that allows using as base algorithms any hierarchical optimization algorithms that would only have simple regret guarantees.

The GPO(A) algorithm (general parallel optimization), whose pseudocode is shown in Algorithm 5, mostly needs to modify the model selection strategy of POO. There are two natural candidates: (i) Lepski's method which is a nested aggregation scheme [START_REF] Lepski | Asymptotically minimax adaptive estimation. I: Upper bounds. optimally adaptive estimates[END_REF][START_REF] Lepski | Optimal pointwise adaptive methods in nonparametric estimation[END_REF][START_REF] Locatelli | Adaptivity to noise parameters in nonparametric active learning[END_REF][START_REF] Locatelli | Adaptivity to Smoothness in X-armed bandits[END_REF] that requires a single optimum, thus not directly applicable to our case, and (ii) a cross-validation scheme that we use and detail in the next. Given a total budget of n function evaluations, GPO(A) runs several instances of A in parallel with parameters chosen in the same grid as that used by POO, each using the same number of evaluations to output a recommendation x i . One half of the budget is then dedicated to estimating the function values at those points, and the one with the highest estimated value is kept.

Algorithm 5: General parallel optimization (GPO)

Input : base algorithm A, budget n, ρ max , ν max , K 1 Compute N = (1/2)D max ln((n/2)/ ln(n/2)) the number of instances 2 for i ← 1, . . . , N do Get n/(2N ) noisy evaluations of f ( x s ) and compute their average

V [s] 6 end 7 s ← arg max s V [s] 8 return x s
In Theorem 8, we provide a general analysis of the GPO algorithm, showing that it attains an (order)optimal simple regret without knowing the parameter triple (ν , C , ρ ) provided that its base algorithm does. As a consequence GPO(HCT) is an alternative to PCT with similar simple regret guarantees.

Theorem 8 If for all (ν, ρ) the A(ν, ρ) algorithm has its simple regret bounded as

E S A(ν,ρ) n ≤ αC (log n/n) 1/(d(ν,C,ρ)+2) , (2)
for any function f satisfying Assumption 1 with parameters (ν, ρ), then there exists a constant β that is independent of ν max and ρ max such that

E S GPO(A) n ≤ βD max (ν max /ν ) Dmax (log 2 n)/n) 1/(d(ν ,C ,ρ )+2) ,
for any function f satisfying Assumption 1 with parameters ν ≤ ν max and ρ ≤ ρ max .

Proof We start by fixing some notation. Recall that N (that depends on n) is the number of instances run in parallel. For j ∈ {1, . . . , N }, we let x j denote the point recommended by the instance A(ν max , ρ j ) with ρ j = ρ 2N/(2j+1) max

. Let (r i,j ) 1≤i≤n + be the i.i.d. evaluations of f ( x j ) used during the validation phase, with n + n/(2N ) and µ n + ,j = 1

n + n +
i=1 r i,j be the estimated value of f ( x j ) computed by the algorithm. We let

 = arg max j µ n + ,j and  = arg max j f ( x j )
be the index of the empirical best and true best among the recommended point. We notice that for any j, {r i,jf ( x j )} n + i=1 is a bounded i.i.d. sequence with zero mean (conditionally to x j ) thus using Hoeffding's inequality one can show that for all ∆ > 0,

P µ n + ,j -f ( x j ) > ∆ ≤ 2 exp -2n + ∆ 2 . By integrating over ∆ ∈ [0, 1], we get ∀j ∈ {1, . . . , N }, E µ n + ,j -f ( x j ) ≤ π/2 √ n + • (3)
As in the analysis of POO, the instance  defined as

 arg min j≤N :ρ j ≥ρ [d(ν max , C , ρ j ) -d(ν , C , ρ )]
shall play a crucial role. Indeed, inequality ( 2) is exactly what is needed in Appendix B.2 and Appendix B.3 of [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] to control the simple regret of that instance in terms of (ν , C , ρ ).

Following the exact same steps, we can show that for some constant α,

E S A(νmax,ρ  ) (n/2N ) ≤ αD max (ν max /ν ) Dmax (log 2 n)/n) 1/(d(ν ,C ,ρ )+2) . (4)
We now turn our attention to the simple regret of GPO(A) after n function evaluations.

E S GPO n = E f -f ( x  ) = E[f -f ( x  )] + E f ( x  ) -f ( x  ) + E f ( x  ) -f ( x  ) . (5)
The first term in ( 5) is equal to the simple regret of the instance  that uses n/N samples, which is upper bounded in (4). The second term in ( 5) is always negative by definition of  and the third term can be rewritten as

E f ( x  ) -f ( x  ) = E f ( x  ) -µ n + ,  + E µ n + ,  -µ n + ,  + E µ n + ,  -f ( x  ) . (6)
where the first and the third term of (6) are both upper bounded by ( π/2)/ √ n + using (3), and the second term is always negative by definition of . Putting things together yields

E S GPO n ≤ αD max (ν max /ν ) Dmax (log 2 n)/n 1/(d(ν ,C ,ρ )+2) + O √ N √ n •
The conclusion follows by observing that the second term in the right-hand side is negligible with respect to the first.

Experimental illustrations

We run experiments on several test functions comparing the original POO along with several instances of HOO and our new instantiation PCT along with HCT instances of different ρ values. In these experiments, we set ρ max = 0.9, and we add Gaussian noise to the function evaluations with a relatively small variance (σ = 0.1).

Artificial landscapes

We test the algorithms on some functions from the artificial landscapes, including (i) two functions with many local minima: Himmelblau function and Rastrigin function, (ii) one valley-shaped function: Rosenbrock function, and (iii) Branin function (see Figure 1). Note that the Rastrigin function shown is its 2D version. In our experiments, we use a Rastrigin function in 5D.

In Figure 2, we plot the simple regret of the algorithms as a function of the number of evaluations. All the results are averaged over 5000 runs and we plot the simple regret after 500 function evaluations. Each instance of HOO or HCT would recommend a point picked uniformly at random among those evaluated so that we have the same recommendation strategy as POO and PCT.

The first observation is that PCT does match the performance of some single HCT instances as expected. We also notice that PCT has comparable performance w.r.t. POO in these plots, which justifies the choice of using HCT as a subroutine for the POO meta-algorithm.

Discussion

We studied PCT, a new instantiation of POO on top of HCT. We proved that HCT is a plausible subroutine for POO by adapting the analysis of HCT under a new assumption w.r.t. a fixed partitioning. We also proposed GPO, a general framework for making any hierarchical bandit algorithm that only has a simple regret guarantee adaptive to unknown smoothness. However, whether it is possible to weaken the assumptions of HOO in the same way as HCT while keeping similar regret guarantees remains open. A.2. Maximum depth of the tree (proof of Lemma 4) Lemma 4 The depth of the covering tree produced by HCT after n function evaluations satisfies

H(n) ≤ H max (n) 1 2(1 -ρ) log nν 2 c 2 ρ 2 •
Proof The deepest tree that can be constructed by HCT is a linear one, where at each level one unique node is expanded. In such case, |I + h (n)| = 1 and |I h (n)| = K for all h < H(n). Therefore, we have

n = H(n) h=0 i∈I h (n) T h,i (n) ≥ H(n)-1 h=0 i∈I + h (n) T h,i (n) ≥ H(n)-1 h=0 i∈I + h (n) T h,i (t h,i ) ≥ H(n)-1 h=0 i∈I + h (n) τ h (t h,i ) definition of t h,i ≥ H(n)-1 h=0 c 2 ν 2 ρ -2h
ineq. ( 7) (n) .

≥ (cρ) 2 ν 2 ρ -2H(n) H(n) since h ≤ H(n) -1 ≥ (cρ) 2 ν 2 ρ -2H
By solving this expression, we obtain

H(n) ≤ 1 2 log nν 2 c 2 ρ 2 / log(1/ρ) ≤ 1 2(1 -ρ) log nν 2 c 2 ρ 2 follows from log(1/ρ) ≥ 1 -ρ ≤ 1 2(1 -ρ) log nν 2 c 2 ρ 2
H max (n).

A.3. High-probability event

In Section 3.2, we described the favorable event ξ t . We now define it precisely. We first define a set L t that contains all possible nodes in trees of maximum depth H max (t),

L t T :depth(T )≤Hmax(t)
Nodes(T )

and we recall the definition of the favorable event

ξ t    ∀(h, i) ∈ L t , | µ h,i (t) -µ h,i | ≤ c log(1/ δ(t)) T h,i (t)    •
Next, we prove that our favorable event holds with high probability.

Lemma 9 With c 1 and c defined in Section A.1, for any fixed round t,

P[ξ t ] ≥ 1 - 4δ 3t 6 •
Proof Letting µ h,i,s denote the empirical mean reward of the first s noisy evaluations of f in x h,i , we upper-bound the probability of the complementary event ξ c t as

P[ξ c t ] ≤ (h,i)∈Lt t s=1 P   | µ h,i,s -µ h,i | ≥ c log(1/ δ(t)) s   union bound ≤ (h,i)∈Lt t s=1 2 exp -2c 2 log(1/ δ(t)) Chernoff-Hoeffding inequality = 2 exp -2c 2 log(1/ δ(t)) t|L t | = 2( δ(t)) 2c 2 t|L t | ≤ 2( δ(t)) 2c 2 t2 Hmax(t)+1 = 2( δ(t)) 2c 2 t2 1 2(1-ρ) log nν 2 c 2 ρ 2 +1 Lemma 4 ≤ 8t( δ(t)) 2c 2 tν 2 c 2 ρ 2 1 2(1-ρ) ≤ 8t δ t (ρ/(3ν)) 1/8 ) 8 1-ρ tν 2 (1 -ρ) 4ρ 2 1 2(1-ρ) plugging in values of c and c 1 = 8t δ t 8 1-ρ ρ 3ν 1 1-ρ t 1 2(1-ρ) ν √ 1 -ρ 2ρ 1 1-ρ ≤ 4 3 δt -2ρ-13 2(1-ρ) ≤ 4δ 3t 6 • A.4. Failing confidence bound
We decompose the regret of HCT into two terms depending on whether ξ t holds. Let us define ∆ t fr t . Then, we decompose the regret as

R HCT n = n t=1 ∆ t = n t=1 ∆ t 1 ξt + n t=1 ∆ t 1 ξ c t = R ξ n + R ξ c n .
The failing confidence term R ξ c n is bounded by the following lemma.

Lemma 10 With c 1 and c defined in Section A.1, when the favorable event does not hold, the regret of HCT is with probability 1δ/(5n 2 ) bounded as

R ξ c n ≤ √ n.
Proof We split the term into rounds from 1 to √ n and the rest,

R ξ c n = n t=1 ∆ t 1 ξ c t = √ n t=1 ∆ t 1 ξ c t + n t= √ n+1 ∆ t 1 ξ c t .
The first term can be bounded trivially by √ n since |∆ t | ≤ 1. Next, we show that the probability that the second term is non zero is bounded by δ/(5n 2 ).

P   n t= √ n+1 ∆ t 1 ξ c t > 0   = P   n t= √ n+1 ξ c t   ≤ n t= √ n+1 P[ξ c t ] union bound ≤ n t= √ n+1 δ t 6 Lemma 9 ≤ ∞ √ n δ t 6 dt = δ 5n 5/2 ≤ δ 5n 2 • A.5. Proof of Theorem 2
Theorem 2 Assume that function f satisfies Assumption 1. Then, setting δ 1/n, the cumulative regret of HCT(ν, ρ) after n function evaluations is upper bounded as

E[R HCT(ν,ρ) n ] ≤ αC(log n) 1/(d(ν,C,ρ)+2) n (d(ν,C,ρ)+1)/(d(ν,C,ρ)+2) ,
where α is a numerical constant and C is the constant associated to d(ν, C, ρ).

We now expand (11) on both sides under ξ t . First, we have

U ht,it (t) µ ht,it (t) + νρ ht + c log(1/ δ(t + )) T ht,it (t) ≤ f (x ht,it ) + νρ ht + 2c log(1/ δ(t + )) T ht,it (t) (13)
and the same holds for the parent of the selected node,

U h p t ,i p t (t) ≤ f (x h p t ,i p t ) + νρ h p t + 2c log(1/ δ(t + )) T h p t ,i p t (t) •
By Lemma 5, we know that U h ,i (t) is a valid upper bound on f . If an optimal node (h , i ) is a leaf, then B h ,i (t) = U h ,i (t) is also a valid upper bound on f . Otherwise, there always exists a leaf which contains the maximum for which (h , i ) is its ancestor. Now, if we propagate the bound backward from this leaf to (h , i ) through ( 10), we have that B h ,i (t) is still a valid upper bound on f . Thus for any optimal node (h , i ), at round t under ξ t , we have

B h ,i (t) ≥ f . (14)
We combine ( 14) with ( 11) and ( 13) to obtain

∆ ht,it f -f (x ht,it ) ≤ νρ ht + 2c log(1/ δ(t + )) T ht,it (t) •
The same result holds for its parent,

∆ h p t ,i p t f -f (x h p t ,i p t ) ≤ νρ h p t + 2c log(1/ δ(t + )) T h p t ,i p t (t) •
We now refine the two above expressions. The subroutine OptTraverse tells us that HCT only selects a node when T h,i (t) < τ h (t). Therefore, by definition of τ ht (t), we have

∆ ht,it ≤ 3c log(2/ δ(t)) T ht,it (t) • (15)
On the other hand, OptTraverse tells us that

T h p t ,i p t (t) ≥ τ h p t (t), thus ∆ h p t ,i p t ≤ 3νρ h p t ,
which means that every selected node has a parent which is (3νρ ht-1 )-optimal.

Step 3: Bound on the cumulative regret. We return to term R ξ n and split it into different depths. Let 1 ≤ H ≤ H(n) be a constant that we fix later. We have Notice that the covering tree is K-ary and therefore |I h (n)| ≤ K|I h-1 (n)|. Recall that HCT only selects a node (h t , i t ) when its parent is 3νρ ht-1 -optimal. Therefore, by definition of the nearoptimality dimension,

R ξ n n t=1 ∆ ht,it 1 ξt ≤ H(n) h=0 i∈I h (n) n t=1 ∆ h,i 1 (ht,it)=(h,i) 1 ξt ≤ H(n) h=0 i∈I h (n) n t=1 3c log(2/ δ(t)) T h,i (t) 1 (ht,it)=(h,i) = H h=0 i∈I h (n) n t=1 3c log(2/ δ(t)) T h,i (t) 1 (ht,it)=(h,i) + H(n) h=H+1 i∈I h (n) n t=1 3c log(2/ δ(t)) T h,i (t) 1 (ht,it)=(h,i) ≤ H h=0 i∈I h (n) τ h (t h,i ) s=1 3c log(2/ δ(t h,i )) s + H(n) h=H+1 i∈I h (n) T h,i (n) s=1 3c log(2/ δ(t h,i )) s ≤ H h=0 i∈I h (n) τ h (
|I h (n)| ≤ |KI h-1 (n)| ≤ KCρ -d(h-1) ,
where d is the near-optimality dimension. As a result, for term (a), we obtain that T h,i (n)

≤ n

H(n) h=H+1 i∈I h (n) log 2/ δ t h,i ,
where we trivially bound the second square-root factor by the total number of pulls. Now consider the first square-root factor. Recall that the HCT algorithm only selects a node when T h,i (t) ≥ τ h (t)

for its parent. We therefore have T h,i ( t h,i ) ≥ τ h ( t h,i ) and the following sequence of inequalities,

n = H(n) h=0 i∈I h (n) T h,i (n) ≥ H(n)-1 h=0 i∈I + h (n) T h,i (n) ≥ H(n)-1 h=0 i∈I + h (n) T h,i ( t h,i ) ≥ H(n)-1 h=0 i∈I + h (n) τ h ( t h,i ) ≥ H(n)-1 h=H i∈I + h (n) τ h ( t h,i ) = H(n)-1 h=H i∈I + h (n) c 2 log(1/ δ( t + h,i ))) ν 2 ρ -2h ≥ H(n)-1 h=H i∈I + h (n) c 2 log(1/ δ( t + h,i ))) ν 2 ρ -2H = c 2 ρ -2H ν 2 H(n)-1 h=H i∈I + h (n) log(1/ δ( t + h,i ))) = c 2 ρ -2H ν 2 H(n)-1 h=H i∈I + h (n)
log(1/ δ( max(t h+1,2i-1 , t h+1,2i )

+ )) = c 2 ρ -2H ν 2 H(n)-1 h=H i∈I + h (n)
log(1/ δ(max(t The second and fourth terms in this sum are negative by definition of j and j respectively, while the third and last terms are O( N/n) using the concentration result mentioned above. As for the first term, one has

+ h+1,2i-1 , t + h+1,2i ))) = c 2 ρ -2H ν 2 H(n)-1 h=H i∈I + h (n) max(
E[f -µ  ] = N n E T t=1 (f -r i, ) = N n E R A(νmax,ρ) n/N = E S A(νmax,ρ) n/N
, where again the recommendation rule matters. Using the upper bound (23) obtained in the first part of the analysis permits to conclude by noting that the first term is actually the leading term.

Algorithm 4 :6

 4 POO(A) -parallel optimistic optimization with base algorithm A Input : base algorithm A, ν max ,ρ max , branching factor of the partitioning K Initialization: D max ← ln K/ ln(1/ρ max ), number of function evaluations n ← 0, current number of instances of A: N ← 1, S ← {(ν max , ρ max )} 1 while budget still available do 2 while N ≤ 1 2 D max log(n/(log n)) Continue running A(s) until it has given n N rewards r s,1 , . . . , r s,n/N . A(s) once and update the average reward µ[s]. 12 n ← n + N 13 end 14 s ← argmax s∈S µ[s] return A point sampled u.a.r. from the points evaluated by A(s )

3s

  ← ν max , ρ max 2N/(2i+1) 4 Run A(s) for n/(2N ) time steps and output a recommendation x s 5

Figure 1 :

 1 Figure 1: Benchmark functions 5

Figure 2 :

 2 Figure 2: Simple regret of POO and PCT run for different ρ values.

  h-1) τ h (n) log(2/ δ(n)) = H h=0 KCρ -d(h-1) c 2 log(2/ δ(n)) ν 2 ρ -2h log(2/ δ(n)) ineq. (7) = KCρ d c log(2/ δ(n

  We bound separately the terms (a) and (b). Since t h,i ≤ n, we have(a) ≤ (n)| τ h (n) log(2/ δ(n)).

					H			H
					h=0 i∈I h (n)	τ h (n) log(2/ δ(n)) ≤	h=0	|I h
						1	t h,i )	3c	log(2/ δ(t h,i )) s	ds
		+	H(n) h=H+1 i∈I h (n)	1	T h,i (n)	3c	log(2/ δ(t h,i )) s	ds
		H
	≤	h=0 i∈I h (n)	6c τ h (t h,i ) log(2/ δ(t h,i ))
				H(n)
		+					6c T h,i (n) log(2/ δ(t h,i ))
			h=H+1 i∈I h (n)
								
	= 6c	     	H h=0 i∈I h (n)	τ h (t h,i ) log(2/ δ(t h,i ))	+	H(n) h=H+1 i∈I h (n)	 T h,i (n) log(2/ δ(t h,i ))      .
								(a)	(b)

  log(1/ δ(t

					+ h+1,2i-1 )), log(1/ δ(t + h+1,2i )))
	≥	c 2 ρ -2H ν 2	H(n)-1 h=H i∈I + h (n)	log(1/ δ(t + h+1,2i-1 )) + log(1/ δ(t 2	+ h+1,2i ))
	=	c 2 ρ -2H ν 2	H(n) h=H+1 i∈I + h-1 (n)	log(1/ δ(t + h,2i-1 )) + log(1/ δ(t + h,2i )) 2	change of variables
	=	c 2 ρ -2H 2ν 2	H(n) h=H+1 i∈I + h (n)	log(1/ δ(t

+ h,i )).

Proceedings of Machine Learning Research vol 98:1-27, 2019

This definition is slightly different from the original POO paper, where a coefficient 3 is present instead of 2 due to a technical detail.

The term resolution refers to the maximum variation in the cell. If it is too large, then we need to shrink the volume, thus increase the resolution.

More generally, Theorem 6 holds for any ν ≤ νmax and ρ ≤ ρmax.

Source: https://en.wikipedia.org/wiki/Test_functions_for_optimization

Acknowledgements

The research presented was supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, a doctoral grant of Ecole Normale Supérieure in Rennes, Inria and Otto-von-Guericke-Universität Magdeburg associatedteam north-European project Allocate, and French National Research Agency projects ExTra-Learn (n.ANR-14-CE24-0010-01), BADASS (n.ANR-16-CE40-0002), and BoB (n.ANR-16-CE23-0003).

Appendix A. Detailed regret analysis for HCT under Assumption 1

A.1. Preliminaries

We first fix some constants and introduce some additional notation that are needed for the proof of Theorem 2.

• c 1 (ρ/(3ν)) 1/8 , c 2 1/(1ρ)

• ∀1 ≤ h ≤ H(t) and t > 0, I h (t) denotes the set of all nodes created by HCT at level h up to step t

• ∀1 ≤ h ≤ H(t) and t > 0, I + h (t) denotes the subset of I h (t) which contains only the internal nodes

• At each step t, (h t , i t ) denotes the node selected by the algorithm.

C h+1,Ki-j

• t h,i max t∈C h,i t denotes the last time (h, i) has been selected

t denotes the last time when one of its children has been selected

• For any t, let y t (r t , x t ) be a random variable, we define the filtration F t as a σ-algebra generated by (y 1 , . . . , y t ).

Another important notion in HCT is the threshold τ h on the number of pulls needed before a node at level h can be expanded. The threshold τ h is chosen such that the two confidence terms in U h,i are roughly equivalent, that is,

Since t + is defined as 2 log(t) , we have t ≤ t + ≤ 2t. In addition, log is an increasing function, thus we have

where the first inequality follows from the fact that 0 < δ(t) ≤ 1/2. We begin our analysis by bounding the maximum depth of the trees constructed by HCT.

For the sake of simplicity, we denote d(ν, C, ρ) as d in the rest of this section. We study the regret under events {ξ t } t and prove that

holds with probability 1δ. We decompose the proof into 3 steps.

Step 1: Decomposition of the regret. We start by further decomposing the instantaneous regret into two terms,

The regret of HCT when confidence intervals hold can thus be rewritten as

We notice that { ∆ t } n t=1 is a bounded martingale difference sequence since E ∆ t |F t-1 = 0 and | ∆ t | ≤ 1. Thus, we apply the Azuma's inequality on this sequence and obtain

with probability 1δ/(4n 2 ).

Step 2: Preliminary bound on the regret of selected nodes and their parents. Now we proceed with the bound of the first term R ξ n . Recall that P t is the optimistic path traversed by HCT at round t. Let (h , i ) ∈ P t and (h , i ) be the node which immediately follows (h , i ) in P t . By definition of B-values and U -values, we have

where the last equality follows from the fact that the subroutine OptTraverse selects the node with the largest B-value. By iterating the previous inequality along the path P t until the selected node (h t , i t ) and its parent (h p t , i p t ), we obtain

Since the root, which is an optimal node, is in P t , there exists at least one optimal node (h , i ) in path P t . As a result, we have

In the above derivation, the last equality relies on the fact that for any h > 0, I + h (n) covers all the internal nodes at level h and therefore its children cover I h+1 (n). We thus obtain

On the other hand, we have

. By plugging (17) into above expression, we get

Now if we combine ( 18) with ( 16), we bound R ξ n as

We choose H to minimize the above bound by equalizing the two terms in the sum and obtain

which after being plugged into (19) gives

Finally, combining ( 21), ( 9), and Lemma 10, we obtain

with probability 1δ.

Appendix B. General analysis of POO

We prove Proposition 7 in this section. The analysis of POO originally proposed by [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] consists in two main parts, that can be adapted to any base algorithm satisfying assumption (1) on its cumulative regret. In the following, we assume that ν ≤ ν max and ρ ≤ ρ max .

The first part of the analysis consists in proving that there exists a parameter ρ such that (ν max , ρ) ∈ G and the instance A(ν max , ρ) has its simple regret bounded in terms of the true parameters (ν , ρ ). One important ingredient is the following lemma, which upper bounds the difference between the near-optimality dimension d(ν max , C, ρ) and d(ν , C , ρ ) for ρ > ρ .

Lemma 11 (Appendix B.1 of [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] Under Assumption 1, for any choice of ρ and ρ s.t. 0 < ρ < ρ < 1, we have

Lemma 11 endorses the choice of grid G = {(ν max , ρ 2N/(2i+1) max

) i }, which ensures that ρ arg min

, where C is associated to ρ. A close examination of Appendix B.2 and B.3 of [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] shows that under the assumption

the simple regret of A(ν max , ρ) can also be related to (ν , C , ρ ): for some constant α ,

under assumption described by (1) on the cumulative regret of the base algorithms. Note that ( 22) holds as the recommendation rule ensures that E

The second part of the analysis controls the simple regret of POO(A) by showing that the error made when choosing s = (ν max , ρ) is negligible. We highlight that for this part, having cumulative regret guarantees is crucial. Denoting by (x i,j ) 1≤i≤n/N the successive points selected by algorithm j and (r i,j ) 1≤i≤n/N the reward observed, the final output of POO(A) can be written x = x I,  where I ∼ U({1, . . . , n/N }) and  = arg max j µ j with µ j = (N/n) n/N i=1 r i,j . One can also define  = arg max j µ j with µ j = N n n/N i=1 f (x i,j ) and  to be the index of the instance such that ρ  = ρ. First, some concentration results (see Appendix B.4 of [START_REF] Grill | Black-box optimization of noisy functions with unknown smoothness[END_REF] show that for all j, E[| µ jµ j |] ≤ C/ n/N . The simple regret can then be upper bounded as


EHESP Professor Blanche Le Bihan

Claude Martin

French social and long term care system

As "community care" has no exact equivalent in the French context, the authors focus on one of the major sector of social and community care which concerns elderly people confronted to a reduction of their autonomy, which correspond to the international denomination: long-term care (LTC). It presents the emergence, the current organization and main challenges of this policy in France.

In France, the notion of "community care" (soin communautaire) never developed as such, probably because of the Republican model which insists, since the Revolution of 1789, on the direct link between the State and citizens. Since then, the intermediary bodies were never as recognized as they are in many other nations, in particular anglo-american ones. Even the French expression: "soin à domicile", sounds very different compared to "home-care", as domiciliation refers to an administrative localisation of the caring work, nothing similar to the notion of "home" (Lesemann & Martin, 1993). In the following article, we propose to focus on one of the major sector of social and community care which concerns elderly people confronted to a reduction of their autonomy, which correspond to the international denomination: long-term care (LTC) 2 .

The French LTC policy: a layering process Contrarily to the main sectors of the French social security system, LTC appeared recently as a public problem and a collective risk, which means only at the end of the 1980s. Since the mid-1970s and early 1980s, nevertheless, an important social and political debate emerged concerning the aging of the French population and the challenge to face it (see Box 1), underlying the absence of a specific policy and many overlaps between measures addressed to the handicapped and older old people (Martin, 2003).

Box 1: The demographic argument still represents a main issue until now. According to the current trends, by 2060 one third of French citizens will be over 60, including almost five million people over 85, compared to 1.4 million in 2015 [START_REF] Blanpain | Projections de population à l'horizon 2070[END_REF]. This 1 . For correspondence, claude.martin@ehesp.fr 2 . This article is based on a report [START_REF] Le Bihan | Thematic report on challenges in LTC -France[END_REF] delivered to the European social policy network (ESPN) funded by the European Commission. We use different sections of the report to produce this paper. See the site https://ec.europa.eu/social/main.jsp?catId=1135&intPageId=3589 demographic evolution is due to increased life expectancy combined with the baby-boomers' arrival at old age [START_REF] Lecroart | Projection des populations âgées dépendantes. Deux méthodes d'investigation[END_REF]. Because the probability of becoming dependent increases with age, the number of elderly people is expected to rise from 1.15 million in 2010 to 1.55 million in 2030 and 2.3 million by 2060, corresponding to an estimated 3% of the population.

But this debate, fed by a great number of official reports, never reached a decision to build up a policy until the early 1990s. Then the policy emerged and developed incrementally. We could even consider it as a layering process. This process led to a fragmented system centred on a specific allowance: l'Allocation personnalisée à l'autonomie (APA) (personal allowance for autonomy).

A specific policy measure: The APA Long-term care policy in France is based on a cash-for-care scheme, introduced in the late 1990s as the Specific Allowance for Dependency (1997). Focusing on situations of "dependency"an expression abandoned afterwards, according to its stigmatizing image-, the benefit aimed at meeting the needs of elderly people who were not covered by health insurance (care opposed to cure), by helping them identify their needs and pay for care services. It was reformed in 2002 and became the personal autonomy allowance (Allocation personnalisée d'autonomie -APA). Managed by the départements3 , the APA is paid to any person aged 60 or over who needs assistance to accomplish everyday activities or needs to be continuously watched over. Each of the four levels of dependency gives access to a maximum amount (table 1), which is then adjusted according to the recipient's needs and level of income. At home, the allowance is paid either to finance a specific "care plan" elaborated by a multidisciplinary team (health and social professionals), after an assessment of the needs, or in a residential home. The use of the benefit is controlled and the multidisciplinary teams in the départements are in charge of following up the situation.

The APA represents over €5 billion, of which 70% comes from the département and 30% from the National Solidarity Fund for Autonomy (CNSA), a specific fund created in 2004 to cover partly the needs of both handicapped and dependent elderly people.

A fragmented system

LTC policy in France cuts across different policy sectorshealth, social and medico-social4 and involves several levels of governance: the state, regions, départements and municipalities.

In France, the government defines national health and social policies through legislation, and different territorial levels are involved in managing and funding the two sectors. Regional and local administrations execute national health policies under close supervision from the government through the Social security system, whereas the decentralized French local authoritiesdépartementsare responsible for social policies. In the elderly care sector, the départements have the obligation to define their local policy orientations, finance and implement the national personal autonomy allowance (APA), and regulate care services within their territory. In addition, municipalities can develop specific voluntary measures to support older people.

This first dividing line between the different territorial levels in the governance of the elderly sector has been reshaped by two recent laws. The first in 2004, a law on solidarity and loss of autonomy, which introduced the CNSA (the national solidarity fund for autonomy), a new national institution responsible for funding and implementing policy measures aimed at older and disabled people. The second, in 2009, named "Hospital, Patients, Health Territories" Act, which created a new regional institution representative of central governmentthe ARS (regional health agencies). Encompassing all existing regional and local health administrations, these regional health agencies extended traditionally health-sector-only intervention to the social care sector.

Funding of the system

The funding of the French LTC policy is complex (Vasselle 2008[START_REF] Charpin | Perspectives démographiques et financières de la dépendance : rapport du Groupe 2[END_REF][START_REF] Fragonard | Stratégie pour la couverture de la dépendance des personnes âgées : rapport du Groupe 4[END_REF]). It combines social security funds (social contributions) and local authorities' taxes. According to [START_REF] Renoux | Les comptes de la dépendance en 2011 et à l'horizon 2060[END_REF], taking into account the social care dimension (€9.7 billion), health insurance expenditure (€11 billion), and accommodation in institutions (€7.5 billion), in 2011 the overall cost of public expenditure on LTC policies represented €21 billioni.e. 1.05% of GDP. Including household contributions, in particular for the cost of accommodation in residential homes, estimated at €7 billion, the total budget on this policy comes to around €28 billioni.e. 1.41% of GDP.

"Community care" scheme to support elderly people and their families

A first category concerns services in the social and health sectors that propose solutions for both home-based care and residential care (box 2). A specific formal care work sector has developed in France to provide professional care in the home and in institutions. (3) Private companies in the personal services sector: these require quality certification. Their prices are established freely and subject to a contract drawn up with the cared-for person. In 2008, they represented only 4% of social care workers for elderly people (Marquier 2010b).

(4) Housing facilities (foyer-logement): social establishments, often run by municipalities. These facilities accommodate old people who are mostly autonomous in small adapted apartments to minimize the risks (of fall, in particular). The development of this type of accommodation is a priority of the 2015 "Act on adapting society to an ageing population".

(5) Nursing homes (établissements d'hébergement pour personnes âgées dépendantes, EHPAD, and private nursing homes): in 2015, they cared for 10% of elderly people aged 75 or more and 1/3 of those aged 90 or more. The average cost of EHPAD accommodation varies from €51 to €71 per day [START_REF] Muller | 000 résidents en établissements d'hébergement pour personnes âgées en 2015[END_REF]. A specific allowance (social assistance for accommodation -ASH) may be allocated to the poorest residents to help them pay for the accommodation part.

(7) Day care centres and temporary accommodation concern 4% of elderly people cared for.

According to the DREES survey [START_REF] Muller | 000 résidents en établissements d'hébergement pour personnes âgées en 2015[END_REF], in 2015 728,000 elderly people lived in residential care, which represented an increase of 4.8% compared to 2011. The recent CARE survey [START_REF] Brunel | Les personnes âgées dépendantes vivant à domicile en 2015[END_REF] estimates the number of elderly people living at home between 0.4 million (including only high-level dependency cases) and 1.5 million (also including mid-level dependency cases).

A second category of measures is related to 'coordination' and/or 'integration'. These measures developed to facilitate relations between the different professional actors -health and social care workersand institutional actors involved in LTC policy in France. In this perspective, the "gerontological networks" (réseaux gérontologiques) were created in 1996.

More recently, three different schemes have been introduced in order to facilitate continuity of care: the MAIA (method for integrated care in the sector of autonomy -Méthode d'Action pour l'Intégration d'aide et de soin dans le champ de l'Autonomie), the PAERPA (elderly people at risk of loss of autonomy -Personnes âgées en risque de perte d'autonomie) and the PTA (territorial support platforms for coordination -Plateformes territoriales d'appui).

Defined at the national level and devised to support health and social care professionals in their coordination tasks, the three schemes have different focuses, i.e. prevention, complex situations and a health and/or social care perspective. Coordination is also needed to help elderly people and their families identify existing support and locate the information they need. Local information and coordination centres (Centres locaux d'information et de coordination -CLIC) were created to this end in the early 2000s.

A last category of schemes concerns informal carers. Although families are no longer left alone to cope with their caring responsibilities, public support is not a substitute for family care. According to the HSA survey [START_REF] Soullier | L'implication de l'entourage et des professionnels auprès des personnes âgées[END_REF], 48% of the cared-for are supported by an informal carer only, 20% by professionals only and 32% by both professionals and informal carers. In other words, 8 older cared-for people out of 10 receive at least some support from their relative(s). 44% of these informal carers of elderly (more than 60 year old) are spouses.

In 20% of the cases, the carer is a daughter, in 13% a son, in 13% a mother or a father [START_REF] Weber | Des enquêtes nationales pour connaître l'aide apportée par les proches en raison d'un handicap ou d'un problème de santé[END_REF].

The possibility to outsource a share of the caring activities has entailed the necessity to coordinate the different professionals and the development of informal carers as "care managers" (Da Roit, Le [START_REF] Da Roit | Cash for Care Schemes and the Changing Role of Elderly People's Informal Caregivers in France and Italy[END_REF]. In a context of spending cuts that make the creation of new services difficult, the importance of the role of informal carersrelatives but also neighbours or friendswho deliver care and/or act as care managers of the organization setup was recognized in the 2015 Act on adapting society to an ageing population. In France, public intervention aimed at informal carers is based on measures to support carers in their activities rather than financial compensation. Besides, although the APA can be used to pay a relative (except the spouse), this solution remains marginal (8% of beneficiaries in 2016).

-Carer leaves: concern both elderly and disabled people. -Information services: a national web platform was created in 2013; Local information and coordination centres (CLIC) also give advice to families.

-Respite platforms: propose advice and solutions to the cared-for and their carers.

The Act on adapting society to an ageing population

The 2015 Act on adapting society to an ageing population marks a turning point in the conception of LTC policy. It attempts to move away from a compensating and medical approach to old age, focused on the notion of dependency, which dates back to the 1990s towards a more preventive orientation, including the notion of "healthy ageing" [START_REF] Delaunay | Loi d'adaptation de la société au vieillissement: un pas pour la transition démographique[END_REF]. It is based on three pillars: (1) Anticipating loss of autonomy, prevention and combating isolation among old people (€185 million in 2017); (2) Adapting society to ageing, which includes the launch of a plan to adapt 80,000 private housing units by 2017; renovate residence-accommodation (foyers logements), renamed 'autonomy residences' (€84 million in 2017); (3) Supporting older people facing loss of autonomy, with a priority given to homebased care (€460 million in 2017).

Main long-term care challenges in France

Access and adequacy challenge: Despite the increased capacity of nursing services, temporary housing units and homes for elderly dependent people (6.5% increase in places from 2011 to 2015), several analyses have identified a problem in accessing services (Court of Auditors 2014[START_REF] Fizzala | Dépendance des personnes âgées : qui paie quoi ?, Les dossiers de la Drees[END_REF]. They indicate three main reasons:  The offer of services lacks transparency which means that users find it difficult to identify the most appropriate solution.

 The cost of social care services. Although health services are financially covered by the insurance system, families are often faced with paying considerable additional costs for social care services. In residential care homes, the average remaining cost to be met by residents is estimated at between €1500 and €1750 per month (excluding social housing benefit for the poorest); in the home, APA beneficiaries pay on average €80 per month from their care plan [START_REF] Fizzala | Dépendance des personnes âgées : qui paie quoi ?, Les dossiers de la Drees[END_REF].  Territorial disparities. Although national legislation exists, measures are carried out locally by département councils and regional health agencies (ARS), with important territorial variations. Rural areas in particular offer fewer in-home care services and nursing services than urban areas.

Quality challenge:

In France, the development of a specific care work sector has two main objectives: to support elderly and disabled people and reduce unemployment through the development of a new professional activity sector. These two objectives have proved contradictory, as the quantitative dimension of the second objective is not always matched with quality (Le [START_REF] Bihan | The development of an ambiguous care work sector in France. Between professionalization and fragmentation[END_REF]. The elderly care work sector is part of the larger sector of "personal services" (services à la personne), which focuses on the volume of workers and includes any person providing services to individuals. Although a specific diploma was created at the end of the 1980s (reformed in 2002 and 2016 to improve training), home-based care is still characterized by a low level of care worker training. According to statistics [START_REF] Marquier | Les intervenants au domicile des personnes fragilisées en 2008 ». Home care workers for fragile people in 2008[END_REF], 62 per cent of care workers have no diploma from either the health or social sector.

The quality of residential care is currently being questioned. Despite an increase in the number of residents, staff ratios for care remained the same from 2011 to 2015. Combined with a pricing reform that is complex to put in place, nursing homes currently face considerable difficulties. Strikes have been organized since the end of 2017 and the situation seems deteriorating.

Employment challenge:

This challenge is primarily related to the work-life balance issue. The HSA survey (2008) carried out by DREES (Directorate for Research, Surveys, Evaluation and Statistics) estimated that 4.3 million carers regularly help one or more relative over 60 [START_REF] Soullier | L'implication de l'entourage et des professionnels auprès des personnes âgées[END_REF]. These carers are aged 58 on average and are most frequently women (they represent 57% of carers of older people, but the proportion increases with the level of dependency of the caredfor). The survey also shows that 46% of carers are retired, 39% have a job, 6% are unemployed and 9% do not work. Care investment has an impact on work in terms of stress and tiredness. 11% of carers have reorganized their professional lives by reducing their work hours, resorting to sick leave or changing jobs.

Although there are no specific data on how many working carers take advantage of carer leaves to achieve a satisfactory work-life balance, a recent survey [START_REF] Sirven | Etre aidant et travailler, premiers résultats d'une enquête pilote[END_REF] suggested very low-take up of this type of leave, at only 7% of interviewees. Most carers (between 50% and 80%) were unfamiliar with the leave provisions. In fact, carers tend to use standard leave (sick leave) or even annual leave, rather than specific carer leaves, which is either unpaid or with a low allowance.

The second issue is the employment situation of professional care workers. This is characterized by precarious working conditions and insufficient training, which explains why the sector remains unattractive. The majority of care workers are employed on a permanent contract, which can appear as a secure form of employment. However, this employment stability is only apparent because of the high prevalence of part-time work and situations in which a care worker has several employers [START_REF] Devetter | Employment quality in the sector of personal and household services: status and impact of public policies in France[END_REF]. Care service work still does not provide full-time work, with fewer than 30 per cent of home care workers employed full time [START_REF] Marquier | Les intervenants au domicile des personnes fragilisées en 2008 ». Home care workers for fragile people in 2008[END_REF]. The average length of the working week is 26.1 hours over 4.9 days, with home care workers attending to 6.5 different people in one week -5.4 of whom are elderly. The average wage is €832 per month, but monthly earnings vary significantly when care workers are employed full time (€11905 ) or part time (€717), depending also on whether the structure they belong to is public or private [START_REF] Nahon | Les salaires dans le secteur social et médico-social en 2011. Une comparaison entre les secteurs privé et public[END_REF].

Financial sustainability challenge:

Four main orientations can be identified, with a stress on the involvement of local actors.

 Improving coordination of the existing schemes, organizations, institutions and professionals has been high on the political agenda during the last decade.

 Developing prevention as announced in the 2015 Act on adapting society to an ageing population.

 Using technological solutions: although investment in new technologies as a solution to support elderly people and their family is recent in France (end of 2000s), it is currently presented as a priority. The definition of what is referred to as the 'silver economy' sector encompasses a broad spectrum, from the most sophisticated safety technologies and robotics to the simplest technical aids and remote assistance services for old peoples' housing and mobility. It is presented as a support for home-based care that will also impact growth, industrial development and employment.

 The final question, which cuts across several areas and constitutes the weak point of the 2015 Act, is the issue of funding the proposed policy. The €700-million budget per year is no doubt highly insufficient. In the mid-term, given the predicted demographic changes, the financing principles of the LTC sector therefore remains open. The possibility of creating a 5 th social security branch, which first arose in the 1990s, has come up again. The government, aware of the difficulties of creating a new user contribution, is putting a greater accent on prevention, thus anticipating and reducing the costs of dependency.

Box 2 :

 2 Home-based and residential services for elderly people (1) Home care nursing services (Services de soins infirmiers à domicile, SSIAD): 117,093 places in 2014 (2) Home help and support services (Services d'aide et d'accompagnement à domicile, SAAD) which include non-profit organizations and public social care services. According to the 2011 INSEE employment survey, there were 535,000 home care workers in 2011.

Table 1 : Characteristics of the APA (Personal Autonomy Allowance)

 1

	Eligibility	At least 60 years old
	criteria	Mid to high level of dependency (Gir 4 to Gir 1) according to national assessment
		grid: AGGIR grid which distinguishes 6 levels of dependency.
		Proportional to the level of income: below a monthly income of €800 recipients do
		not contribute to the funding of the care plan; above €2945 of monthly income
		recipients contribute 90% of the funding.
	Amount of the	Gir 1 (highest level of dependency): € 1713 max
	allowance (per	Gir 2: €1375 max
	month)	Gir 3: €931 max
		Gir 4: €662 max

Table 2 : Carer leaves

 2

	Leave	Description	Duration	Payment level Eligibility	Flexibility
					conditions
	Carer Leave To care for	3 months,	Unpaid	To have	Can be used
		relatives with	renewable		worked at least	for a part-
		significant loss	up to one		2 years	time period
		of autonomy	year
	Family	To assist a	3 months,	Unpaid but	Granted to all	Can be used
	Solidarity	dying relative	renewable	daily	employees	for a part-
	Leave		once	allowance		time period
				(€55/day max
				21 days)
	-A right to respite was introduced in the 2015 Act on adapting society to an ageing
	population: max €500/year
	-Training has been available to informal carers since 2009 (2009 Health Law)

. A specific local authority which is intermediary between municipalities and regions and in charge of social policies.

A specific French sector in tandem with the health and social sectors, whereas English only distinguishes "health care" and "social care" sectors.

. Which corresponds to the minimum wage: €1100 per month.


Valeria Bondarenko

Ina Taralova

The algorithm for the analysis of combined chaotic -stochastic processes 1

The algorithm for the analysis of combined chaotic-stochastic processes

Valeria Bondarenko, Ina Taralova

Introduction

The understanding of the dynamic behavior in real physical or industrial system is of almost importance, for analysis, synthesis, prediction, etc. It is sensible to consider that the behavior of many physical systems like phytoplankton, solar activity, oscillation of waves is a combination between chaotic or stochastic processes, which can be successfully used for prediction of health applications, meteorological phenomena etc [START_REF] Achard | Discrete variations of the fractional Brownian in the presence of outliers and an additive noise[END_REF][START_REF] Alos | Stochastic calculus with respect to fractional Brownian motion with Hurst parameter[END_REF]. Many physical/ chemical or sometimes financial phenomena are considered as being only chaotic ((ex. Belousov -Zhabotinsky reaction) or purely stochastic (stock model price, integral Ito, Black-Scholes model), but in fact they could be both deterministic and stochastic [START_REF] Beran | Statistics for Long-Memory Processes Chapman and Hall[END_REF][START_REF] Bezborodov | Option pricing with fractional stochastic volatility and discontinuous payoff function of polynomial growth[END_REF][START_REF] Bondarenko | Approximation of Time Series by Power Function of the Fractional Brownian Motion[END_REF]. So it is of utmost interest to find new models taking into account both behaviors, stochastic and chaotic, to understand and predict better the real physical phenomena, but also to model data for biomedical applications like (ECG, IRM).

The original idea in this paper is to juxtapose methods from stochastic signal analysis (nonstationary Gaussian processes, statistics from limit theorems by Nordin, Hurst exponent), and nonlinear (chaotic) dynamical system analysis (phase portrait, phase delayed plot, Lyapunov exponents), to develop a common methodology to analyze complex time series [START_REF] Biagini | Stochastic calculus for fractional Brownian motion and applications[END_REF][START_REF] Bogachev | Gaussian measures[END_REF][START_REF] Breton | Error bounds on the non-normal approximation of Hermite power variations of fractional Brownian motion[END_REF][START_REF] Breton | Exact condence intervals for the Hurst parameter of a fractional Brownian motion[END_REF]. Assuming that these two behaviors are inherently correlated, we are analyzing if there exists a correlation exists between the stochastic quantifiers (Hurst exponent, Garch method,ARMA) and chaotic quantifiers (Lyapunov exponents) [START_REF] Coeurjolly | Simulation and identication of the fractional Brownian motion: A bibliographical and comparative study[END_REF][START_REF] Coeurjolly | Estimating the parameters of a fractional Brownian motion by discrete variations of its sample paths[END_REF][START_REF] Bondarenko | Forecasting time series for power consumption data in different buildings using the fractional Brownian motion[END_REF]. To do that, different kind of stochastic-chaotic mixed processes shall be modeled and analyzed from different points of view to be developed. The idea is to find new models taking into account both behaviors, stochastic and chaotic, to understand and predict better the real physical phenomena, but also to model data for different applications such as biomedical or financial processes.

Proposed methodology

As classical approach, we assume a priory stochastic nature of time series model and construct a mathematical model as a random process [?]. Hurst exponent is defined like the estimate Ĥ of approximated fractional Brownian motion for these time series. On the other hand, for some deterministic systems, where the state is the solution of nonlinear differential or differ-ence equation like x n = X(t n ), the behavior can be highly irregular and extremely complex. In some cases the behavior is estimated like chaotic. In the first approximation, we can determine the chaocity by the property of the system to construct it's trajectories in a bounded domain of the phase space. Properties of dynamical systems which generate chaotic solutions, have been widely discussed by the authors (results and references in the monographs [START_REF] Lozi | From chaos to randomness via geometric undersampling[END_REF][START_REF] Taralova | Chaotic orbits prediction and atypical bifurcations in a class of piece-wise linear noninvertible maps[END_REF]). The simplest example is an one-dimensional dynamical system x n+1 = f (x n , µ) which generates chaotic solution for some functions f and values of parameter µ . In particular, for logistic function f such as x n+1 = µx n (1 -x n ), the plot of solution looks like white noise with some values µ > 3.6. So, the problem statement the nature of time series analysis nature is do the observed data have stochastic nature, or deterministic. Let B (t), 0 ≤ t ≤ 1 be a fractional Brownian motion with Hurst exponent H. Let's consider the normalized increments

ξ k = n H B k n -B k -1 n ∼ ℵ (0; 1) .
In the series of papers some limit theorems for the functions of these increments were proven. Let's denote

α k = n H B k n = k-1 j=1 ξ j .
There is a mean-square convergence:

1 n n k=1 α k ξ 3 k → - 3 2 , H ∈ 0; 1 2 , 1 n 1+H α 2 k ξ 3 k → 3η , H ∈ 0; 1 2 , (1)
where

η ∼ ℵ 0; 1 2H + 2 ; 1 n 2H n k=1 α k ξ 3 k → 3 2 B 2 (1) , H ∈ 1 2 ; 1 .
Let's normalize the increments and assume:

z k = (σ) -1 n H y k = 0.8 R 1n y k .
We assume that the hypothesis T holds:

z k = ξ k = n H B k n -B k -1 n . (2)
Assume

v k = k-1 j=1
z j and calculate the statistical indexes:

A n = 1 n v k z 3 k , H ∈ 0; 1 2 ; B n = 1 n 1+H v 2 k z 3 k , H ∈ 0; 1 2 ; D n = 1 n 2H v k z 3 k , H ∈ 1 2 ; 1 . (3)
If hypothesis T is true, then there is convergence:

A n → -1.5 ; B n → 3η ; D n → 3 2 B 2 (1)
.

The decision about the hypothesis T is taken by comparing the actual values of statistics with their limiting theoretical values. Let's determine the deviation from the limit value δ = |A n + 1.5| for statistic A n ; the limit distribution functions for statistics B n , D n :

F 1 (x) = P {3η < x} = Φ x 3d , F 2 (x) = 2Φ 2 3 x -1 , x > 0 ,
where Φ is Laplace function, d = (2H + 2) -0.5 . Hypothesis T is accepted, if

δ < β 0 , |B n | < β 1 , H < 0.5 ; 0 < D n < β 2 , H > 0.5 , (4)
where β 1 , β 2 are quantiles of distributions of F 1 , F 2 , corresponding to the selected level of significance α = 0.1. Then,

β 1 = 4.95 √ 2H + 2 , β 2 = 4.08 .

Results and discussion

The rate of convergence of statistics to the limit has been tested by numerical experiment for the first example ("ideal case"):

z k = σ-1 n H (X (k) -X (k -1)) ; X (t) = σB H (t) ,
where the values of fractional Brownian motion were obtained by simulation.

The values of the statistical indexes A n , B n , D n are shown in Table 1.

|B n | < 4.95 √ 2H + 2 = β B , H < 0.5 ; 0 < D n < 4.08 = β D , H > 0.5 ,
and deviation δ, H < 0.5, is an increasing function of H (for H = 0.4, δ ≈ 1).

The second example is a deterministic logistic chaotic sequence x k+1 = 4x k (1 -x k ), k = 1, . . . , 1049. By procedure of estimation, we obtained Ĥ = 0.15. The statistical indexes are as follows: A n = 0.6 > 0, |B n | = 1.9 > β B = 0.08. Hypothesis T is rejected.

The third example. Assume that the observed values are an additive mixture of the deterministic chaotic and random sequences:

x k = u k + av k ,
where u k are the values of a dynamical system, v k are the values of a random process. Sequences {u k }, {v k } are normalized by energy, therefore

1 n u 2 k = 1 n v 2 k = 1.
Then, the value a determines stochastic share in the observed data. In the example,

u k = 4u k-1 (1 -u k-1 ), v k = σB H k n .
The stochastic sequence v k is generated with H f Bm = 0.1-0.9. Table 2 shows estimate Ĥ of mixture and values of statistical indexes. The table data show the "aggressiveness" of the chaotic component in relation to stochastic for H f Bm ≥ 0.2. Inequalities (4) are not satisfied for these values of fBm and character of the mixture determines the logistic sequence. The deviation of statistics from the limit values is the same as for the "pure" fractional Brownian motion (Table 1) (for H f Bm = 0.1). Persistence ( Ĥ > 0.5) of investigated time series (D n < β 2 ) means it has stochastic nature; antipersistent ( Ĥ = 0.1-0.2, A n ≈ A, |B n | < β 1 ) admits the existence of the chaotic component (values tend to revert to a mean: an increase is likely to be followed by a decrease and vice-versa).

Conclusion

The mixed chaotic-stochastic sequence has been successfully analyzed with statistical tools. The increments of the sequence have been approximated as a random variable, after pre-processing. The agressiveness of the chaotic component has been estimated for the case of anti-persistant f Bm approximation, and the statistical indexes have been identified.

Table 1 :

 1 Values of statistical indexes

	H	A n	B n	D n	β 1
	0.1 n = 200 -1.30 0.84		3.34
	n = 1000 -1.32 2.63		3.34
	0.2 n = 200 -1.21 0.81		3.20
	n = 1000 -1.35 1.74		3.20
	0.3 n = 200 -2.00 0.37		3.07
	n = 1000 -1.10 0.50		3.07
	0.4 n = 200 -0.55 1.26		2.96
	n = 1000 -2.51 0.83		2.96
	0.6 n = 200			1.75
	n = 1000			1.03
	0.7 n = 200			1.23
	n = 1000			0.67
	0.8 n = 200			1.05
	n = 1000			0.52
	0.9 n = 200			0.48
	n = 1000			0.04
	From Table 1, it follows that

Table 2 :

 2 Statistical indexes of mixture (a = 1, a = 2, n = 2000)

	H	H	A n	B n	D n	β 1
	0.1 a = 1 0.6 -1.94 -0.07 -0.43 2.77
		a = 2 0.1 -1.60 -0.40 -697 3.34
	0.2 a = 1 0.15 -5.35 -15.3 -1095 3.26
		a = 2 0.15 -3.19 -6.17 -652 3.26
	0.3 a = 1 0.6 -2.54 -0.12 -0.56 2.77
		a = 2 0.2 -5.0 -9.20 -477 3.19
	0.4 a = 1 0.15 -4.50 -7.38 -920 3.26
		a = 2 0.15 -2.33 -1.03 -475 3.26
	0.6 a = 1 0.6 -0.91 -0.01 -0.20 2.77
		a = 2 0.15 -4.0	15.8	-813 3.26
	0.7 a = 1 0.6 -1.35 -0.03 -0.30 2.77
		a = 2 0.1 -1.08 0.47	-470 3.34
	0.8 a = 1 0.6 -1.37 -0.03 -0.30 2.77
		a = 2 0.6 -0.68 -0.01 -0.15 2.77
	0.9 a = 1 0.6 -1.45 -0.03 -0.32 2.77
		a = 2 0.6 -1.91 -0.07 -0.42 2.77