Stochastic Simultaneous Optimistic Optimization Michal Valko [email protected] INRIA Lille - Nord Europe, SequeL team, 40 avenue Halley 59650, Villeneuve d’Ascq, France Alexandra Carpentier [email protected] Statistical Laboratory, CMS, Wilberforce Road, CB3 0WB, University of Cambridge, United Kingdom
arXiv:2604.24537v1 [cs.LG] 27 Apr 2026
Rémi Munos [email protected] INRIA Lille - Nord Europe, SequeL team, 40 avenue Halley 59650, Villeneuve d’Ascq, France
Abstract
One motivation for this setting is a measurement error when dealing with a stochastic environment. Another example is the optimization of some parametric policy operating in a stochastic system.
We study the problem of global maximization of a function f given a finite number of evaluations perturbed by noise. We consider a very weak assumption on the function, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global maxima. Compared to previous works on bandits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.
We assume that there exists at least one global maximizer x∗ ∈ X of f , i.e. f (x∗ ) = supx∈X f (x). We aim for an algorithm which sequentially evaluates f at points x1 , x2 , . . . , xn in the search space X to find a good approximation to a global maximum. After n function evaluations the algorithm outputs a point x(n) and its performance is measured with the loss: Rn = sup (f (x)) − f (x(n))
1. Introduction We consider a function maximization problem of an unknown function f : X → R. We assume that every function evaluation is costly, and therefore we are interested in optimizing the function given a finite budget of n evaluations. Moreover, the evaluations are perturbed by noise, i.e., the evaluation of f at a point xt ∈ X returns a noisy evaluation rt , assumed to be independent from the previous ones, such that: E[rt |xt ] = f (xt ).
(2)
x∈X
(1)
Proceedings of the 30 th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013. JMLR: W&CP volume 28. Copyright 2013 by the author(s).
Our definition of loss is very related to the simple regret in multi-armed bandits (Bubeck et al., 2009). Many algorithms have been developed for this general optimization problem. However, a lot of them require some assumption on the global smoothness of f , most typically, they assume a global Lipschitz property (Pintér, 1995; Strongin & Sergeyev, 2000; Hansen & Walster, 2004; Kearfott, 1996; Neumaier, 2008). There has been also an interest in designing sample-efficient strategies, only requiring local smoothness around (one) of the global maxima (Kleinberg et al., 2008; Bubeck et al., 2011a; Munos, 2011). However, these approaches still assume the knowledge of this smoothness, i.e., the metric under which the function is smooth, which may not be available to the optimizer. Recently, Munos (2011) proposed the SOO algorithm for deterministic optimization, that assumes that f is locally smooth with respect to some semi-metric ℓ, but that this semi-metric does not need to be known to the algorithm. SOO extends the DIRECT algorithm (Jones et al., 1993) and other Lipschitz optimization without the knowledge of the Lipschitz constant (Bubeck et al., 2011b; Slivkins, 2011) to the case of any possible semi-metric by simultaneously considering the subspaces that can contain the optimum.
Stochastic Simultaneous Optimistic Optimization
In this paper, we provide an extension of SOO to the case of noisy evaluations, which we call Stochastic SOO, or StoSOO. One major difference from SOO is that we cannot base our exploration strategy only on a single evaluation per cell since we are dealing with stochastic functions. Another difference is that we cannot simply return the highest evaluated point we encountered as x(n) since it is subject to noise. Our analysis shows that in a large class of functions (precisely defined in Section 5), the loss of StoSOO is Õ(n−1/2 ), which is of same order as the loss of HOO (Bubeck et al., 2011a) or Zooming algorithm (Kleinberg et al., 2008) when using the best possible metric.
2. Background Optimistic optimization refers to approaches that implement the optimism in the face of uncertainty principle. This principle became popular in the multi-armed bandit problem (Auer et al., 2002) and was later extended to the tree search (Kocsis & Szepesvári, 2006; Coquelin & Munos, 2007) where it is referred to as hierarchical bandit approach. The reason is that a complex problem such as global optimization of the space X is treated as a hierarchy of simple bandit problems. It is therefore an example of Monte Carlo tree search which was shown to be empirically successful for instance in computer Go (Gelly et al., 2012). Optimistic optimization was also used in many other domains, such as planning (Hren & Munos, 2008; Bubeck et al., 2011a) or Gaussian process optimization (Srinivas et al., 2010). This paper applies optimistic approach to a global black-box function optimization. Table 1 displays representative approaches for this setting. The case when the smoothness of the function f is known, means that the function is either (globally) Lipschitz, weakly Lipschitz or locally Lipschitz around the optimum. There are numerous algorithms for this setting, the most related to our work are DOO (Munos, 2011) for the deterministic case and Zooming (Kleinberg et al., 2008) or HOO (Bubeck et al., 2011a) for the stochastic one1 . This setting has been also considered in a Bayesian framework, in particular the expected-improvement strategy (Osborne, 2010) which was theoretically analyzed when the assumption of smoothness is data-driven (Bull, 2011). One of the disadvantages of these algorithms is that however strong or mild are the assumptions on f , the quantities that express them (i.e. a prior, a Lipschitz constant, or a semi-metric in DOO) need to be known 1
Note that the loss (2) considered here is different but related to the usual cumulative regret defined in the bandit setting, see e.g. (Bubeck et al., 2009).
Table 1. Hierarchical optimistic optimization algorithms
deterministic
stochastic
known smoothness
DOO
Zooming or HOO
unknown smoothness
DIRECT or SOO
StoSOO
this paper
to the algorithm. On the other hand, for the case of deterministic functions there exist approaches that do not require this knowledge, such as DIRECT or SOO. However, neither DIRECT nor SOO can deal with stochastic functions. Therefore, we extend the SOO algorithm to the stochastic setting and provide a finitetime analysis of its performance.
3. Algorithm StoSOO is a tree-search based algorithm that iteratively constructs finer and finer partition of the search space X . The partitions are represented as nodes of a K-ary tree T and the nodes are organized by their depths h ≥ 0, with h = 0 being the root node, and indexed by 1 ≤ i ≤ K h . We denote ◦[h, i], the i-th node at depth h. Each of the nodes ◦[h, i] corresponds to a cell Xh,i ⊆ X in the partitioning, i.e., to a subset of X with an associated representative point xh,i ∈ Xh,i . 3.1. Assumptions We now state our main assumption, which is also used in SOO (Munos, 2011). The first part of the assumption is about the existence of a semi-metric ℓ such that the function f is locally smooth with respect to it. We stress that although it quantifies the smoothness of f , it only requires the existence of ℓ and not the knowledge of it. For illustrative examples and discussion on this part we refer the reader to (Munos, 2011). The second part is about the structure of the hierarchical partitioning with respect to ℓ. This partitioning is fixed and given to the algorithm as a parameter. Assumption There exists a semi-metric ℓ : X ×X → IR+ (i.e. for x, y ∈ X , we have ℓ(x, y) = ℓ(y, x) and ℓ(x, y) = 0 if and only if x = y) such that: A1 (local smoothness of f ): For all x ∈ X : f (x∗ ) − f (x) ≤ ℓ(x, x∗ ).
(3)
A2 (bounded diameters and well-shaped cells): There exists a decreasing sequence w(h) > 0, such
Stochastic Simultaneous Optimistic Optimization
that for any depth h ≥ 0 and for any cell Xh,i of depth h, we have supx∈Xh,i ℓ(xh,i , x) ≤ w(h). Moreover, there exists ν > 0 such that for any depth h ≥ 0, any cell Xh,i contains a ℓ-ball of radius νw(h) centered in xh,i . Assumption A1 guarantees that f does not decrease too fast around one global optimum x∗ . This can be thought of as a one-sided local Lipschitz assumption. Note that although we require that (3) is satisfied for all x ∈ X , this assumption essentially sets constraints to the function f locally around x∗ , since when x is such that ℓ(x, x∗ ) > sup f −inf f , then the assumption is automatically satisfied. Thus when this property holds, we say that f is locally smooth with respect to ℓ around its maximum. Assumption A2 assures the regularity of the partitioning, in particular that the size of the cells decreases with their depths and that their shape is not skewed in some dimensions. 3.2. Stochastic SOO Algorithm 1 displays the pseudo-code of the StoSOO algorithm. The algorithm operates in the traversals of the tree starting from the root down to the current depth(T ), that is upper bounded by hmax , a parameter of the algorithm. During each traversal (a whole pass of the “for” cycle) StoSOO selects a set of promising nodes, at most one per depth h. These nodes are then either evaluated or expanded. Evaluating a node at time t means sampling the function in the representative point xh,i of the cell Xh,i and observing the evaluation rt according to (1). Expanding a node ◦[h, i], means splitting its corresponding cell into its K sub-cells corresponding to the children: {◦[h + 1, i1 ], ◦[h + 1, i2 ], . . . , ◦[h + 1, iK ]}. We denote by L the set of leaves in T , i.e. the nodes with no children. At any time, only the leaves are eligible for an evaluation or expansion and we never expand the leaves beyond depth hmax . If the function f were deterministic, such as in SOO (Munos, 2011), we would expand (simultaneously) any leaf ◦[h, i] whose value f (xh,i ) is the largest among all leaves of the same or a lower depth. The reason for this choice is that by Assumption A1 all such nodes may contain x∗ . Unfortunately, we do not receive f (xh,i ), but only a noisy estimate rt . Therefore, the main algorithmic idea of StoSOO is to evaluate the leaves several times in order to build a confident estimate of f (xh,i ). For this Pt purpose, let us define µ̂h,i (t) = Th,i1 (t) s=1 rs 1{xs ∈ Xh,i } the empirical average of rewards obtained at
Algorithm 1 StoSOO Stochastic Simultaneous Optimistic Optimization Parameters: number of function evaluations n, maximum number of evaluations per node k > 0, maximum depth hmax , and δ > 0. Initialization: T ← {◦[0, 0]} {root node} t ← 0 {number of evaluations} while t ≤ n do bmax ← −∞ for h = 0 to min(depth(T ), hmax ) do if t ≤ n then For each leaf ◦[h, j] ∈p L, compute its b-value: bh,j (t) = µ̂h,j (t) + log(nk/δ)/(2Th,j (t)) Among leaves ◦[h, j] ∈ Lt at depth h, select ◦[h, i] ∈ arg max bh,j (t) ◦[h,j]∈L
if bh,i (t) ≥ bmax then if Th,i (t) < k then Evaluate (sample) state xt = xh,i . Collect reward rt (s.t. E[rt |xt ] = f (xt )). t←t+1 else {i.e. Th,i (t) ≥ k, expand this node} Add the K children of ◦[h, i] to T bmax ← bh,i (t) end if end if end if end for end while Output: The representative point with the highest µ̂h,j (n) among the deepest expanded nodes: x(n) = arg max µ̂h,j (n) s.t. h = depth(T \ L). xh,j
state xh,i at time t, where Th,i (t) is the number of times that ◦[h, i] has been sampled up to time t. StoSOO builds an accurate estimate of f (xh,i ) before ◦[h, i] is expanded. To achieve this, we define an upper confidence bound (or a b-value) for each node ◦[h, i] as: s log(nk/δ) def bh,i (t) = µ̂h,i (t) + , (4) 2Th,i (t) where δ is the confidence parameter. In the case of Th,i (t) = 0, we let bh,i (t) = ∞. We refer to p log(nk/δ)/2Th,i (t) as to the width of the estimate. Now instead of selecting the promising nodes according to their values f (xh,i ) we select them according to their b-values bh,i .
Stochastic Simultaneous Optimistic Optimization
Our algorithm is optimistic since it considers such leaves for the selection whose b-value is maximal among leaves at depth h or lower depths, since those leaves are likely to contain the optimum x∗ at time t, given the observed samples and Assumption A1 on f . The important question is now how many times should we evaluate the node before we decide to expand it. Again, if we knew the semi-metric ℓ we would be able to calculate the appropriate count for each depth h. Since we do not know it, we instead evaluate each node a fixed number of k times before its expansion. We address the setting of k, hmax , and δ in Sections 4 and 5. Our analysis shows that under appropriate assumptions on f (discussed in Section 5) we √ can bound the expected regret as E[Rn ] = O log2 (n)/ n by setting p √ k = n/ log3 (n), hmax = n/k, and δ = 1/ n. In the algorithm, we keep track of the number of evaluations t in order to finish when it reaches n, the maximum number of evaluations, i.e., the budget. Since we are facing a stochastic setting, we cannot simply output the value that received the highest reward during n evaluations, as it is the case in most of the deterministic approaches. Instead, we return the representative point xh,j of the node with the highest estimate µ̂h,j (n) among the deepest expanded nodes, i.e., such that h = depth(T \ L).
4. Analysis In this section we analyze the performance of StoSOO and upper bound the loss (2) as a function of the number of evaluations. We assume that the rewards are bounded2 by |rt | ≤ 1 for any t. In order to derive a loss bound we define a measure of the quantity of nearoptimal states, called near-optimality dimension. This measure is closely related to similar measures (Kleinberg et al., 2008; Bubeck et al., 2008). For any ε > 0, let us write the set of ε-optimal states as: def
Xε = {x ∈ X , f (x) ≥ f ∗ − ε}.
define the event in which this occurs and then show that this event happens with high probability. Lemma 1. Let ξ be the event under which all average estimates are within their widths: n def ξ = ∀h, i, t s.t. h ≥ 0, 1 ≤ i < K h , 1 ≤ t ≤ n, and s log(nk/δ) o Th,j (t) > 0 : µ̂h,j (t) − f (xh,j ) ≤ , 2Th,j (t) then P(ξ) ≥ 1 − δ. Proof. Let m denote the (random) number of different nodes sampled by the algorithm up to time n. Let τi1 be the first time when the i-th new node ◦[Hi , Ji ] is sampled, i.e., at time τi1 −1 there are only i−1 different nodes that have been sampled whereas at time τi1 , the i-th new node ◦[Hi , Ji ] is sampled for the first time. Let τis , for 1 ≤ s ≤ THi ,Ji (n), be the time when the node ◦[Hi , Ji ] is sampled for the s-th time. Moreover, we denote Yis = rτis − f (xHi ,Ji ). Using this notation, we rewrite ξ as: ( ξ=
∀i, u s.t. , 1 ≤ i ≤ m, 1 ≤ u ≤ THi ,Ji (n), u
1X i Y ≤ u s=1 s
r
) log(nk/δ) . 2u
(5)
Now, for any i and u, the (Yis )1≤s≤u are i.i.d. from some distribution νHi ,Ji . The node ◦[Hi , Ji ] is random and depends on the past samples (before time τi1 ) but the (Yis )s are conditionally independent given this node and consequently: ! r u 1X i log(nk/δ) P Y ≤ = u s=1 s 2u r X u log(nk/δ) 1 i ◦ [Hi , Ji ] = E◦[Hi ,Ji ] P Y ≤ u s=1 s 2u ≥1−
δ , nk
Definition 1. The ν-near-optimality dimension is the smallest d ≥ 0 such that there exists C > 0 such that for any ε > 0, the maximum number of disjoint ℓ-balls of radius νε and center in Xε is less than Cε−d .
using Chernoff-Hoeffding’s inequality. We finish the proof by taking a union bound over all values of 1 ≤ i ≤ n and 1 ≤ u ≤ k.
StoSOO maintains the upper confidence bounds (bvalues) for each cell in order to decide which cell to sample or expand. We start by quantifying the probability that all the average estimates µ̂h,j (t) are at any time t within those bh,j (t)-values. For this purpose we
Lemma 1 shows that when the leaf is expanded then with high probability the mean estimate µ̂h,j (t) is very close to its true value. Specifically, when the node is expanded then with probability 1 − δ uniformly for all h, j, and t, we have that:
2 The analysis can be easily extended to the case when the noise is sub-Gaussian.
|µ̂h,j (t) − f (xh,j )| ≤ ε,
(6)
Stochastic Simultaneous Optimistic Optimization
p where ε = log(nk/δ)/2k. We use this lemma to show that the expanded nodes are with high probability close to optimal. Definition 2. Let the expansion set at depth h be the set of all nodes that could be potentially expanded before the optimal node at depth h is expanded:3 def
Ihε = {nodes ◦[h, i] such that f (xh,i )+w(h)+2ε ≥ f ∗ }. Recall that even though this definition uses w(h) that depends on the unknown metric ℓ, the StoSOO algorithm does not need to know it. Now, let us denote h∗t the deepest depth of the expanded node at time t, that contains the optimum x∗ . Notice that in general the algorithm may have at time t also expanded some (suboptimal) nodes in the deeper depths. In the following, we show that they are not too many of these. Specifically, for each depth h, we lower bound the number of evaluations after which the h∗t needs to be at least h. Lemma 2. Let depth h ∈ {0, hmax } be any depth and: def
th = (k + 1)hmax (|I0ε | + |I1ε | + · · · + |Ihε |). After we evaluated at least t ≥ th nodes, then in the event ξ, the depth h∗t of the deepest node in the optimal branch is at least h, i.e., h∗t ≥ h. Proof. By induction on h. For h = 0, the lemma holds trivially since h∗t ≥ 0. For the induction step, let us assume that the lemma holds for all h ∈ {0, . . . , h′ }, where h′ < hmax and we are to show it holds for h′ + 1 as well. Assume we have already evaluated th′ +1 nodes, i.e. that we are at time t ≥ th′ +1 . Since th is increasing in h, we have also evaluated th′ nodes and h∗t ≥ h′ from the induction step. That means that the optimal branch is expanded at least up to the depth h′ . Now consider any node ◦[h′ + 1, i] at depth h′ + 1, that was expanded. If it was expanded before the optimal node ◦[h′ +1, i∗ ] at depth h′ +1 was expanded, then bh∗t +1,i (t) ≥ bh∗t +1,i∗ (t). According to Lemma 1, the average estimates µ̂h,j (t) are at most ε away from their true values, with ε defined in (6). Therefore in the event ξ, the true values of the expanded and the optimal node are at most 2ε apart: f (xh∗t +1,i ) ≥ f (xh∗t +1,i∗ ) − 2ε.
(7)
Since the node ◦[h∗t + 1, i∗ ] contains the optimum x∗ , then by Assumptions A1-2, we get: f (xh∗t +1,i∗)+w(h+1) ≥ f (xh∗t +1,i∗)+ℓ(xh∗t +1,i∗ , x∗ ) ≥ f ∗. 3
The reason for such definition will become apparent in the proof of Lemma 2.
Combining this with (7), we obtain that: f (xh∗t +1,i ) ≥ f (xh∗t +1,i∗ ) − 2ε ≥ f ∗ − w(h∗t + 1) + 2ε .
This means that all the nodes ◦[h′ + 1, i] expanded before ◦[h′ + 1, i∗ ] are [w(h∗t + 1) + 2ε]-optimal. By Definition 2, there are exactly |Ihε′ +1 | such nodes. Each traversal of the tree in the StoSOO algorithm selects one of these nodes for evaluation. Since k evaluations are required before the expansion, after (k + 1)|Ihε′ +1 | traversals, ◦[h′ + 1, i∗ ] must have been expanded. To guarantee this many traversals, we need (k + 1)hmax |Ihε′ +1 | evaluations after t′h previous evaluations. This is equal to th′ +1 and thus h∗t ≥ h′ + 1. Lemma 2 bounds the number of needed evaluations in the terms of the expansion set sizes to assure that the optimal node was expanded. Naturally, we would like to know, how big these expansion sets can be. The following lemma upper bounds the size of expansion sets up to depth where w(h) is of the order of ε. For this purpose, we define hε as: hε = arg min{h ∈ N : w(h + 1) < ε}.
(8)
Lemma 3. Let d be a ν/3-near-optimality dimension and C the related constant. Then for each h ≤ hε , the cardinality of the expansion set at depth h is in the event ξ bounded as: −d
|Ihε | ≤ C (w (h) + 2ε)
.
Proof. By contradiction. Assume that for some h ≤ −d hε , |Ihε | > C (w (h) + 2ε) . By definition of |Ihε |, each representative point xh,i of the node ◦[h, i] is [w(h) + 2ε]-optimal. By Assumption A2, each cell associated with the node ◦[h, i] at depth h contains a ball of radius νw(h) = ν3 · 3w(h) ≥ ν3 (w(h) + 2ε) with the representative point xh,i , because for h ≤ hε , we have that ε ≤ w(h) by (8). Since the cells are disjoint, we have a contradiction with ν/3-near-optimality dimension being d. We now link the depth of the tree after n iterations with the loss as defined in (2). Theorem 1. Assume that Assumptions A1-2 hold. Let d be the ν/3-near-optimality dimension and C be the corresponding constant. Then the loss of StoSOO run with parameters k, hmax , and δ > 0, after n iterations is bounded, with probability 1 − δ, as: Rn ≤ 2ε + w (min (h(n) − 1, hε , hmax )) p where ε = log(nk/δ)/(2k) and h(n) is the smallest h ∈ N, such that: C(k + 1)hmax
h X l=0
−d
(w (l) + 2ε)
≥ n.
Stochastic Simultaneous Optimistic Optimization
Proof. Let us first consider the case when h(n) − 1 ≤ hε . Then we can use Lemma 3 to show that: h(n)−1
n > C(k + 1)hmax
X
−d
(w (l) + 2ε)
l=0
w(hε ) = cγ hε +1 /γ = w(hε + 1)/γ < ε/γ.
h(n)−1
≥ (k + 1)hmax
X l=0
the deeper is the node we return, the lower regret p we can incur. This suggests the choice of √ hmax = n/k, √ in which case we get h(n) ≥ n/(2C k) − 1, since k ≥ 1. Moreover, since w(h) = cγ h , then by definition of hε we have that:
|Ilε | = th(n)−1
(9)
If h(n) − 1 ≤ hmax then by Lemma 2, h∗n ≥ h(n) − 1. If, however, h(n) − 1 > hmax , then by (9) the algorithm has expanded all potentially optimal nodes on the level hmax and therefore h∗n ≥ hmax . Nonetheless the algorithm does not go beyond hmax , so necessarily h∗n = hmax . Hence, in the case when h(n) − 1 ≤ hε , h∗n ≥ min{h(n) − 1, hmax }. Now consider the opposite case, i.e., when h(n) − 1 ≥ hε + 1. We can now use Lemma 3, but only up to depth hε , to get that n > thε . Similarly to the previous case, we deduce that h∗n ≥ min{hε , hmax }. Altogether, h∗n ≥ min{h(n)−1, hε , hmax }. Let ◦[h, j] be the deepest node that has been expanded after n evaluations. We know that h ≥ h∗n . Let also ◦[h∗n , i∗ ] be the optimal node at the depth h∗n . As ◦[h, j] was expanded, the true value of its representative point and the representative point of ◦[h∗n , i∗ ] is in the event ξ at most 2ε away and therefore we conclude that: f (xh,j ) ≥ f (xh∗n ,i∗ ) − 2ε ≥ f ∗ − [w(h∗n ) + 2ε] ∗
≥ f − [w(min{h(n) − 1, hε , hmax }) + 2ε].
5. The important case d = 0 We now deduce the following corollaries for the case when the near-optimality dimension d = 0 and the diameters w(h) are exponentially decreasing. We postpone the discussion about this important case d = 0 to Section 5.1. Corollary 1. Assume that the diameters of the cells decrease exponentially fast, i.e., w(h) = cγ h for some c > 0 and γ < 1. Assume that the ν/3-near-optimality dimension is d = 0 and let C be the corresponding constant. Then the expected loss of StoSOO run with p parameters k, hmax = n/k, and δ > 0, is bounded as: √ E[Rn ] ≤ (2 + 1/γ)ε + cγ n/k min{0.5/C,1}−2 + 2δ. (10) −d Proof. When d = 0, then w(l) + 2ε = 1 and by definition of h(n), we have that n ≤ C(k + −d Ph(n) 1)hmax l=0 w(l) + 2ε = C(k + 1)hmax (h(n) + 1), which implies h(n) ≥ n/(C(k+1)hmax )−1. Intuitively,
By Theorem 1, we have that in the event ξ, the regret of StoSOO is at most: Rn ≤ 2ε + w(min{h(n) − 1, hε , hmax })
≤ 2ε + w(hε ) + w(min{h(n) − 1, hmax }) √ ≤ (2 + 1/γ)ε + cγ n/k min{0.5/C,1}−2
We obtain the upper bound on the expected loss (10), by considering that by Lemma 1, ξ holds with probability 1 − δ and |rt | ≤ 1.
Corollary 2. For the choice k = n/ log3 (n) and δ = √ 1/ n, we have: log2 (n) √ E[Rn ] = O . n
This result shows that, surprisingly, StoSOO achieves the same rate Õ(n−1/2 ), up to a logarithmic factor, as the HOO algorithm run with the best possible metric, although StoSOO does not require the knowledge of it. √ Proof. Setting k = n/ log3 (n) and δ = 1/ n we can upper bound ε in (10) which was defined in (6) as: s r r √ log(nk/δ) log(nk n) log3 (n) 5 log2 (n) √ ε= = ≤ . 2k 2n 4 n Now for n bigger than a quantity exponential in C/ log(1/γ), the second term in (10) becomes negligible and the upper bound for this choice follows. 5.1. Some intuition about the case d = 0 We have seen that the near-optimality dimension d is a property of both the function and the semi-metric ℓ. Since StoSOO does not require the knowledge of the semi-metric ℓ (it is only used in the analysis), one can choose the best possible semi-metric ℓ, possibly according to the function f itself, in order to have the lowest possible value of d. The case d = 0 thus corresponds to the following assumption on f : there exists a semi-metric ℓ such that: 1) f is locally smooth w.r.t. ℓ around a global optimum x∗ (i.e. such that (3) holds) 2) the diameters of the cells (measured with ℓ) decrease exponentially fast, and 3) there exists C > 0 such that for any ε > 0, the maximal number of disjoint ℓ-balls of radius νε/3 centered in Xε is less than C (i.e. the near-optimality dimension d is 0).
Stochastic Simultaneous Optimistic Optimization 1.2
1.2
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
−0.2
−0.2 0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Figure 1. Functions with d = 0. Left: Two-sine product function f1 (x) = 12 (sin(13x) · sin(27x)) + 0.5. Right: Garp land function: f2 (x) = 4x(1 − x) · ( 43 + 14 (1 − | sin(60x)|)).
5.2. Examples Let us consider the case of functions f defined on [0, 1]D that are locally equivalent to a polynomial of degree α around their maximum, i.e., f (x) − f (x∗ ) = Θ(∥x − x∗ ∥α ) for some α > 0, where ∥ · ∥ is any norm. The choice of semi-metric ℓ(x, y) = ∥x − y∥α implies that the near-optimality dimension d = 0. This covers already a large class of functions (such as the functions plotted in Figure 1: the two-sine product function for which α = 2 and the non-Lipschitz garland function for which α = 1/2). More generally, we consider a finite dimensional and bounded space, i.e., such that X can be packed by CX ε−D ℓ-balls with radius ε (e.g., Euclidean space [0, 1]D ) and such that X has a finite doubling constant (defined as minimum value q such that every ball in X can be packed by at most q balls in X of half the radius). Let a function in such space have upper- and lower envelope around x∗ of the same order (Figure 2), i.e., there exists constants c ∈ (0, 1), and η > 0, such that for all x ∈ X : min(η, cℓ(x, x∗ )) ≤ f (x∗ ) − f (x) ≤ ℓ(x, x∗ ).
In the opposite case when ε ≥ η, the radius of disjoint ℓ-balls that could possibly pack Xε is at least η. Noting that Xε ⊂ X , we can upper bound the packing number of the whole space X , by a constant CX (η)−D that is independent of ε. Finally, defining C = max{C ′ , CX (η)−D } we have that for all ε, the maximum number of disjoint ℓ-balls of radius ε and center in Xε is less than a C and therefore d = 0. Even more generally, one can even define the semimetric ℓ according to the behavior of f around x∗ in order that (3) holds. For example if the space X is a normed space (with norm ∥ · ∥), one can define the def
metric ℓ(x, y) = ℓ̃(∥x − y∥) for any r ≥ 0 as: ℓ̃(r) =
sup x;∥x∗ −x∥≤r
[f (x∗ ) − f (x)] .
Thus f (x∗ ) − ℓ(x, x∗ ) naturally forms a lower-envelope of f . Thus assuming that the first inequality of (11) (upper-envelope) holds, then d = 0 again. However, although the case d = 0 is quite general, it does not hold in situations where there is a discrepancy between the upper- and lower-envelopes (Figure 3).
(11)
We show that all such functions have a near-optimality dimension d = 0 according to Definition 1, (where ν = 1 for simplicity), which means that for all ε > 0, the packing number of Xε is upper-bounded by a constant. f (x∗ ) − cℓ(x, x∗ )
f (x∗ )
have that: Xε ⊂ {x : cℓ(x, x∗ ) ≤ ε}, which corresponds to an ℓ-ball centered in x∗ with radius ε/c. This ball can be packed by no more than a constant number of C ′ ℓ-balls of radius ε. C ′ is necessarily finite because the doubling constant q is finite. For example in [0, 1]D , if ℓ(x, y) = ∥x − y∥∞ then C ′ = (1/c)D .
f (x∗ ) − η f (x∗ ) − ℓ(x, x∗ )
x∗
Figure 2. Any function satisfying (11) lies in the gray area and possesses a lower- and upper-envelopes that are of same order around x∗ .
In the case when ε < η, due the upper envelope we
Figure 3. We illustrate the case of a function with different order in the upper and lower envelopes, when ℓ(x, y) = √ √ |x−y|α . Here f (x) = 1− x+(−x2 + x)·(sin(1/x2 )+1)/2. The lower-envelope behaves like a square root whereas the upper one is quadratic. The maximum number of ℓ-balls with radius ε that can pack Xε (i.e., Euclidean balls with radius ε1/α ) is at most of order ε1/2 /ε1/α ≤ ε−3/2 , since α ≤ 1/2 in order to satisfy (3). We deduce that there is no semi-metric of the form |x − y|α for which d < 3/2.
6. Experiments In this section we numerically evaluate the performance of StoSOO4 . In all experiments with set the parameters k, δ, and hmax to the values from Corollary 2. 4
code available at https://sequel.lille.inria.fr/Software/StoSOO
Stochastic Simultaneous Optimistic Optimization
Moreover, we set the branching factor to K = 3. Note that when the branching factor is an odd number (K ≥ 3), we can reuse the evaluations (samples) from the parent node. Indeed, if K is odd, the representative point of the parent node ◦[h, i] will have the same value as the middle child ◦[h + 1, (K + 1)/2], i.e., xh,i = xh+1,i(K+1)/2 . In the case when the domain of f is multi-dimensional, we only need to split along one dimension at the time, when expanding the node. In order to preserve bounded diameters assumption, we can split each time along the dimension in which the cell is the largest. For the evaluation we added a truncated (so that rewards are bounded) zero mean Gaussian noise NT , sample of which is shown in Figure 4. In all the experiments we performed 10 trials and the error bars in the figures correspond to standard deviations. 1.2
1.2
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
−0.2
−0.2
However, (stochastic) DOO needs to know the semimetric ℓ in order to define w(h). We evaluate the performance of this stochastic DOO using two semimetrics that satisfy Assumption A1: ℓ1 (x, y) = 12|x − y| (for which d = 1/2) and ℓ2 (x, y) = 144|x − y|2 (for which d = 0). We observe that StoSOO performs as well as stochastic DOO for the better metric without the knowledge of it. Garland function: Next, we consider a garland function displayed in Figure 1 (right). The optimization of this function is challenging because f2 is not Lipschitz for any L. However its near-optimality dimension is still d = 0 (Section 5.2). Figure 7 shows the performance of StoSOO as we vary the number of the evaluations. Notice a higher variance at iteration 200 in the left plot; this is because for that many iterations, StoSOO was able to reach the depth h = 6 but only for a few nodes (while only h = 5 for less iterations) with small number of ⌈200/(log3 (200))⌉ = 2 evaluations. 0.3
0.3
0.25
0.25
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Figure 4. Functions from Figure 1 noised with NT (0, 0.1).
0.15
0.4
0.4
0.4
0.35
0.35
0.35
0.3
0.3
0.1
0.1
0.05
regret (loss)
regret (loss)
regret (loss)
0.2
0.15
0.2 0.15
0.25
0.2
0.15
0
0.1
0.05
0.05
0.05
0
10
50
100
500
number of function evaluations
1000
−0.05
200
300
400
500
600
700
800
900
1000
number of function evaluations
0
100
200
300
400
500
600
700
800
900
1000
number of function evaluations
Figure 7. StoSOO’s performance for the garland function. Left noised with NT (0, 0.01). Right: Noised with NT (0, 0.1).
7. Conclusion
0.1 0.1
100
0.3
0.25 0.25
0.15
0.05
0
Two-sine product: In the first set of experiments we consider a two-sine product function displayed in Figure 1 (left) maximized for f (0.867526) ≈ 0.975599. Figure 5 displays the performance of StoSOO for different levels of noise. We observe that as we increase the number of evaluations, the regret of StoSOO decreases.
0.2
regret (loss)
0.1
regret (loss)
0.2
0
10
50
100
500
0
1000
10
number of function evaluations
50
100
500
1000
number of function evaluations
Figure 5. StoSOO’s performance for function f1 . Left: Noised with NT (0, 0.01). Middle: Noised with NT (0, 0.1). Right: Noised with NT (0, 1). 0.6
0.5
0.4
regret (loss)
In Figure 6, we compare StoSOO to the straightforward stochastic version of DOO (Munos, 2011), where we expand each node after log(n2 /δ)/(2w(h)2 ) evaluations (i.e. when the size of the confidence interval becomes smaller than the diameter w(h) of the cell).
0.3
0.2
We presented the StoSOO algorithm that is able to optimize black-box stochastic functions, without the knowledge of their smoothness. We derived a finitetime performance bound on the expected loss for the important case when there exists a semi-metric such that the near-optimality dimension d = 0. We showed that this case corresponds to a large class of functions. In such cases, the performance is almost as good as with an algorithm that would know the best valid semimetric. In the future we plan to derive finite-time performance for the case d > 0.
0.1
0
−0.1
10
50
100
500
1000
number of function evaluations
Figure 6. StoSOO (diamonds) vs. Stochastic DOO with ℓ1 (circles) and ℓ2 (squares) on f1 .
8. Acknowledgements This research work presented in this paper was supported by European Community’s Seventh Framework Programme (FP7/2007-2013) under grant agreement no 270327 (project CompLACS).
Stochastic Simultaneous Optimistic Optimization
References Auer, Peter, Cesa-Bianchi, Nicolò, and Fischer, Paul. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2-3):235–256, 2002. Bubeck, Sébastien, Munos, Rémi, Stoltz, Gilles, and Szepesvári, Csaba. Online Optimization of X-armed Bandits. In Neural Information Processing Systems (NeurIPS), pp. 201–208, 2008. Bubeck, Sébastien, Munos, Rémi, and Stoltz, Gilles. Pure Exploration in Multi-armed Bandits Problems. Algorithmic Learning Theory, pp. 23–37, 2009. Bubeck, Sébastien, Munos, Rémi, Stoltz, Gilles, and Szepesvari, Csaba. X-armed bandits. Journal of Machine Learning Research, 12:1587–1627, 2011a. Bubeck, Sébastien, Stoltz, Gilles, and Yuan, YuJia. Lipschitz bandits without the Lipschitz constant. In Algorithmic Learning Theory, pp. 144–158. Springer, 2011b.
Kearfott, R Baker. Rigorous Global Search: Continuous Problems. Nonconvex Optimization and Its Applications. Springer, 1996. Kleinberg, Robert, Slivkins, Alexander, and Upfal, Eli. Multi-armed bandit problems in metric spaces. In Proceedings of the 40th ACM symposium on Theory Of Computing, pp. 681–690, 2008. Kocsis, Levente and Szepesvári, Csaba. Bandit based Monte-Carlo Planning. In Proceedings of the 15th European Conference on Machine Learning, pp. 282–293. Springer, 2006. Munos, Rémi. Optimistic Optimization of Deterministic Functions without the Knowledge of its Smoothness. In Neural Information Processing Systems (NeurIPS), pp. 783–791, 2011. Neumaier, Arnold. Interval Methods for Systems of Equations. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2008.
Bull, Adam. Convergence rates of efficient global optimization algorithms. The Journal of Machine Learning Research, 12:2879–2904, 2011.
Osborne, Michael. Bayesian Gaussian processes for sequential prediction, optimisation and quadrature. PhD thesis, University of Oxford, 2010.
Coquelin, Pierre-Arnaud and Munos, Rémi. Bandit Algorithms for Tree Search. In Uncertainty in Artificial Intelligence, pp. 67–74, 2007.
Pintér, János. Global Optimization in Action: Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications. Nonconvex Optimization and Its Applications. Springer, 1995.
Gelly, Sylvain, Kocsis, Levente, Schoenauer, Marc, Sebag, Michèle, Silver, David, Szepesvári, Csaba, and Teytaud, Olivier. The grand challenge of computer Go: Monte Carlo tree search and extensions. Commun. ACM, 55(3):106–113, March 2012. Hansen, Eldon and Walster, William. Global Optimization Using Interval Analysis: Revised and Expanded. Pure and Applied Mathematics Series. Marcel Dekker, 2004. Hren, Jean-Francois and Munos, Rémi. Optimistic Planning of Deterministic Systems. In European Workshop on Reinforcement Learning, pp. 151–164, 2008. Jones, David, Perttunen, Cary, and Stuckman, Bruce. Lipschitzian optimization without the Lipschitz constant. Journal of Optimization Theory and Applications, 79(1):157–181, 1993.
Slivkins, Aleksandrs. Multi-armed bandits on implicit metric spaces. In Neural Information Processing Systems (NeurIPS), pp. 1602–1610. 2011. Srinivas, Niranjan, Krause, Andreas, Kakade, Sham, and Seeger, Matthias. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. International Conference on Machine Learning (ICML), pp. 1015–1022, 2010. Strongin, Roman and Sergeyev, Yaroslav. Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Nonconvex Optimization and Its Applications. Springer, 2000.