Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization
Authors: Wenjie Li
Chi-Hua Wang
Guang Cheng
Qifan Song
Venue: Accepted by TMLR ()

Abstract: In this paper, we make the key delineation on the roles of resolution and statistical uncertainty in hierarchical bandits-based black-box optimization algorithms, guiding a more general analysis and a more efficient algorithm design. We introduce the optimum-statistical
collaboration, an algorithm framework of managing the interaction between optimization error flux and statistical error flux evolving in the optimization process. We provide a general analysis of this framework without specifying the forms of statistical error and uncertainty quantifier. Our framework and its analysis, due to their generality, can be applied to a large family of functions and partitions that satisfy different local smoothness assumptions and have different numbers of local optimums, which is much richer than the class of functions studied in prior works. Our framework also inspires us to propose a better measure of the statistical uncertainty and consequently a variance-adaptive algorithm VHCT. In theory, we prove the algorithm enjoys rate-optimal regret bounds under different local smoothness assumptions; in experiments, we show the algorithm outperforms prior efforts in different settings.

Published in Transactions on Machine Learning Research (05/2023)
Optimum-statistical Collaboration Towards General and Ef- ficient Black-box Optimization
Wenjie Li
li3549@purdue.com edu
Department of Statistics, Purdue University
Chi-Hua Wang
chsheaawang@uulle edu
Department of Statistics, University of Californio, Los Angles
Guang Cheng
muangcheng@ucke edu
Department of Statistics, University of California, Los Angles
Qifan Song
afsong edu
Department of Statistics, Purdue University
Reviewed on OpenReview: https: openreveew. net/ forum? id= Cd=CUIcmudlan
Abstract
In this paper, we make the key delineation on the roles of resolution and statistical un- certainly in hierarchical bandits-based black-box optimization algorithms, guiding a more general analysis and a more efficient algorithm design. We introduce the aptimum-statistiun collaboration, an algorithm framework of managing the interaction between optimization er- flxx and statistical error flux evolving in the optimization process. We provide general analysis of this framework without specifying the forms of statistical error and uncertainty quantifier. Our framework and its analysis, due to their generality, can be applied to large family of functions and partitions that satisfy different local smoothness assumptions and have different numbers of local optimums, which is much richer than the class of functions studied prior works. Our framework also inspires us to propose better measure of the statistical uncertainty and consequently a variance-adaptive algorithm VHCT. In theory, we prove the algorithm enjoys rate-optimal regret bounds under different local smoothness assumptions; in experiments, we show the algorithm outperforms prior efforts in different settings.
Introduction
Black-box optimization has gained more and more attention nowadays because of its applications in large number of research topics such as tuning the typer-parameters of optimization algorithms, designing the hidden structure of deep neural network, and resource investments (Li et al., 2018 Komljenovic et al. 2019). Yet, the task of optimizing a black-box system often has a limited budget for evaluations due to expensiveness, espccially when the objective function nonconvex and can only be evaluated by an estimate with uncertainty (Bubeck et al.] 2011b Grill al. 2015). Such limitation haunts practitioners' deployment of machine learning systems and invites scientists' investigation for the authentic roles of resolution (opti- mization error) and uncertainty (statistical error) in black-box optimization. Indeed, it raises question of optimum-statistical trade-off: how can we better balance resolution and uncertainty along the search path to create efficient black-box optimization algorithms?
Among different categorics of black-box optimization methods such as Bayesian algorithms (Shahriari et al. 2016 Kandasamy et al. 2018)) and convex black-box algorithms (Duchi al.) 2015 (Saain 2015). this paper focuses the class of hierarchical bandits-based optimization algorithms introduced by Auur et. al.

---

Published in Transactions on Machine Learning Research (05/2023)
1.0
-014
0.0
00
-04
0.4
00
-06
-07
(a) Difficult function
Function 1/(mx)
Figure 1: ((a) difficult function proposed by Grill et al. (2015 which has exponentially increasing regions in the standard partition. [(b] An example function that violates the v1p"
local smoothness assumption by Grill et al. (2015) in the standard partition and thus cannot be analyzed by prior works, but has no local optimum.
2007 Bubeck et al. 2011b). These algorithms search for the optimum by traversing a hierarchical partition of the parameter space and look for the best node inside the partition. Existing results, such as Bubeck al. (2011b); Grill al. (2015); Shang et al. (2019); Bartlett al. (2019); Li al. (2022), heavily rely on some specific assumptions of the smoothness of the blackbox objective and the hierarchical partition. However, their assumptions
only satisfied by small class of functions and partitions, which limits the scope of their analysis. To be more specific, existing studies all focus on optimizing rexponentially-loaassmoooo
functions (see; Eqn. (3), ) which can have an exponentially increasing number of sub-optimums as the parameter space partition proceeds deeper (Grill et al. 2015 Shang et al.) 2019 Bartlett et al. 2019). For instance, Grill et al. 2015 designed a difficult function (shown in Figure [(a) that can optimized by many existing algorithms because it satisfies the exponential local-smooth assumption. However, functions and partitions that do not satisfy exponential local-smoothness, but with a bounded
polynomially increasing number of near-optimal regions have been overlooked in the current literature of black-box optimization. A simple example is Figure [(b] which is not exponentially smooth but has a trivial unique optimum. Such simple example depresses all previous analyses in existing studies due to their dependency on the exponential local- smoothness assumption. What is worse, different designs of the uncertainty quantifier can generate different algorithms and thus may require different analyses. Consequently, more unified theoretical framework to manage the interaction process between the optimization error flux and the statistical error flux desirable and beneficial towards general and efficient black-box optimization.
In this work, deliver generic perspective on the oplimum-statisticaal collaboration inside the exploration mechanism of black-box optimization. Such a generic perspective holds regardless of the local smoothness condition of the function or the design of uncertainty quantification, generalizing its applicability to a larger class of functions (e.g., Figure I(b) and algorithms with different uncertainty quantification methods. Our analysis for the proposed general algorithmic framework only relies on mild assumptions. allows us analyze functions with different levels of smoothness and also inspired us propose variance-adaptive black-box algorithm VHCT.
In summary, our contributions are:
We identify two decisive components of exploration in black-box optimization: the resolution descriplor (Definition [] and the uncertainty quantifier (Definition 2]. Based on the two components, we introduce the optimum-statistica collaboration (Algorithm [], a generic framework for collaborated optimism hierarchical mandits-bssed black-box optimization.
We provide unified analysis of the proposed framework (Thcorem 3.1 that is independent the specific forms of the resolution descriptor and the uncertainty quantifier. Due the flexibility of the resolution descriptor, this analysis includes all black-box functions who satisfy the general local smoothness assump-
2

---

Published in Transactions on Machine Learning Research (05/2023)
tion (Condition GLS and have finite near-optimality dimension (Definition 1 which are excluded from prior works.
Furthermore, the framework inspires us to propose a better uncertainty quantifier, namely the variance- adaptive quantifier (VHCT). It leads to effective exploration and advantages our bandit policy by utilizing the variance information learnt from past samplers. Theoretically, show that the proposed framework secures different regret guarantees in the face of different smoothness assumptions, and VHCT leads to a better convergence when the reward noise is small. Our experiments validate that the proposed variance adaptive quantifier more efficient than the cxisting anytime algorithms on various objoctives.
Related Works. Pioncer bandit-based black-box optimization algorithms such as HOO (Bubock et al. 2011b) and HCT (Azar et al. 2014) require complicated assumptions of both the the black-box objective and the parameter partition, including weak lipschitzness assumption. Recently, Grill et al. (2015) proposed the exponential local smoothness assumption (Eqn. (3)) to simplify the set of assumptions used in prior works and proposed POO to meta-tune the smoothness parameters. Some follow-up algorithms such as GPO (Shang
et al. 2019) and Stroqu00L (Bartlett. et. al.) 2019) also proposed. However, both GPO and Stroqu00L require the budget number beforehand, and thus they not anytime algorithms (Shang et al. 2019 Bartlett et al.
2019 Also, the analyses of these algorithms all rely on the exponential local smoothness assumption
(Grill et al. 2015
2
Preliminaries
Problem Formulation. We formulate the problem optimizing implicit objective function X x R, where X' is the parameter space. The sampling budget (number of evaluations) is denoted by an unknown constant n, which is often limited when the cost of evaluating f(x) is expensive. At each round (evaluation) t, the algorithm selects a 24 E X and receives an stochastic feedback rı E [0,1], modeled by
rt f(x)) +
where the noise e is only assumed to be mean zero, bounded by [- 2 for some constant > 0, and independent from the historical observed algorithm performance and the path of selected zy's. Note that the distributions of 6 are not necessarily identical. We assume that there exists at least one point xx e X such that it attains the global maximum f", i.e., f f(x") suPaex (x)) The goal of black-box optimization algorithm is to gradually find vn such that fIx) is close to the global maximum f within the limited budget.
Regret Analysis Framework. We measure the performance of different algorithms using the cumulative regret. With respect to the optimal value f", the cumulative regret is defined as
Rn = nf
Tt is worth noting that an alternative measure of performance widely used in the literature (e.g., Shang et al. 2019 Bartlett et al. 2019) is the simple regret S, = f"- - rr. Both simple and cumulative regrets measure the performance of the algorithm but are from different aspects. The former one focuses on the convergence of the algorithm's 's final round output, and the latter cares about the overall loss during the whole algorithm training. The cumulative regret is useful in scenarios such as medical trials where ill paticnts are included in the each run and the cost of picking non-optimal treatments for all subjects shall be measured. This paper chooses to study the cumulative regret, while in the literature, there were discussions on the relationship between these two [Bubeck et al. 2011a).
Hierarchical partitioning. We use the hierarchical partitioning P (Pr.c] to discretize the parameter space X' into nodes, as introduced by Munos (201I); Bubeck et al. (2011b): Valko et al. (2013). For any non-ncgative integer h, the set (Pr.) partitions the whole space X. At depth h 0, a single node Po.1 covers the entire space. Every time we increase the level of depth, each node at the current depth level will be separated into two children; that is, Pr.i P1t112i-1 1,2 Such hierarchical partition naturally
3

---

Published in Transactions on Machine Learning Research (05/2023)
inspires algorithms which explore the space by traversing the partitions and selecting the nodes with higher rewards to form tree structure, with Po.1 being the root. We remark that the binary split. for each node we consider in this paper is the same as in the previous works such as Bubeck et al. 2011b); [zar et al. (2014). and it would be easy to extend our results to the K-nary case (Shang et al. 2019 Similar to Grill et al. (2015), we refer to the partition where each node split into regular, same-sizen children as the standard partitioning.
Given the objective function and hierarchical partition P, introduce generalized definition of near- optimality dimension, which is natural extension of the notion defined by Grill et al. (2015).
Near-optimality dimension. For any positive constants a and C, and any function E(h) that satisfies Yh 2 1, E(h) E 1], we define the near-oplimality dimension d = d(a,, C,E(h) of with respect to the partition P and function E(h) as
d i= > 0: vh 2 0,Na(oE(h) S (E(h)-*)
(1)
if exists, where (e) is the number of nodes Ph.; level h such that supxeP,, f(x) 2 -
In other words, for each h > 0, (h))((h))) is the number of near-optimal regions on level h that are (hE( close to the global maximum so that any algorithm should explore these regions. = día, C,E(h) controls the polynomial growth of this quantity with respect to the function E(h)- It can be observed that this general definition of d covers the near optimality dimension defined in Grill et al. (2015) by simply setting g(h) = p² and the coefficient
2v for some constants 0 and p E (0, 1).
The rationale of introducing the generalized notion E(h) is that, although the number of nodes in the partition grows exponentially when h increases, the number of near-optimal regions Na(e) of the objective function f may not increase as fast, even if the near-optimal gap converges to 0 slowly. The particular choice of E(h) = p² in Grill et al. (2015) indicates that Ni(ap") I Cp which may be over-pessimistic and makes a non-ideal setting for analyzing functions that, change rapidly and don't have exponentially many opar-optimal regions.
Such generalized definition becomes extremely useful when dealing with functions that have different local smoothness properties, and therefore our framework can successfully analyze much larger class of functions. We establish our general regret bound based on this notion of ncar-optimality dimension in Theorem 3.1
It worth mentioning that taking a slowly decreasing E(h), although reduces the mumber of near-optimal regions, does not necessarily imply that the function easier to optimize. As will be shown in Section 3 and 4 {(h) often taken be the local smoothness function of the objective. A slowly decreasing {(h) makes the function much more unsmooth than a function with exponential local smoothness, and hence is still hard to optimize.
Additional Notations. At round f, we use Htt to represent the maximum depth level explored in the partition by an alm.rithm. For each node Ph.i, we use Tl,:(() to denote the number of times it has been pulled and r (2H,)) to denote the k-th reward observed for the node, evaluated at a pre-specified æn,i within Ph,i, which the same as in Azar et al. (2014); [haang et al. (2019). Note that in the literature, it is also considered that rh,s follows some distribution supported on Ph. e.g., Bubeck et al. (2011b).
3 Optimum-statistical Collaboration
This section defines two decisive quantities (Resolution Descriptor and Uncertainty Quantifier) that play important roles in the proposed optimum-statistica collaboration framework. We then introduce the general optimum-statistical collaboration algorithm and provide its theoretical analysis.
Definition 1. (Resolution Descriptor OE). Define OE, to be the resolution for each level h, which is a function that bounds the change of ff around its global optimum and mcasures the current optimization error, i.e., for any global optimum x².
vh 0, Vx
f(x*) -Oa;
(OE)
where Pr.g is the node level h in the partition that contains the global optimum x².
4

---

Published in Transactions on Machine Learning Research (05/2023)
Algorithm Optimum-Statisticall Collaboration (OSC)
Input:
parlition P, resolution descriptor OE,; uncertainty quantifier : (),, selection policy T())
Initialize ( Pl,1. P1,2}
for t to do
4: S (Po.), Phene = Pu,1
5: while OE,, 2 SE (T,t) do
6:
S (Ph.n U (,2 Ph++ +126)
7: T(S) selects a new node Phese from S
end while
Pull Phoii and update SE (T,
10: if ОE 2 SE (T, and Ph, 1,22, $ T then
11:
T= U (Ph,+122 P1,+1
12: end if
13: end for
Definition 2. (Uncertainty Quantifier SE). Let SE,, (T,t) be the uncertaindy estimate for the node PA, at time i, which aims to bound the statistical estimation error of [(x,,,, given T pulled values from this node. Recall that (t) is the number of pulls for node Ph. until time t, and let (t, be the online estimator f(naa), we expect that SE ensures E P(Af)) < for some constant C, where
A = (vh, (t). f(xn,s)) S SEA, (Th.
=
(SE)
With a slight abuse of notation, we rewrite (Th,, t) as ST,, t) when no confusion is caused. When (t) = 0, (T, is naturally taken to be to0 since the node is nover pulled. To ensure the above probability requirement holds, it is reasonable to make (T, + 1) 2 (T,,:(T,t) because when the number of pulls 7 fixed, the statistical error should not decrease.
Given the above definitions of the resolution descriptor and the uncertainty quantifier at each node, we introduce the ceciimum-statistinnn collaboration algorithm in Algorithm that guides the tree-based optimum search path, under different settings of OE and SE.
The basic logic behind Algorithm is that at each time t, the selection policy TS) will contimuuusy search nodes from the root leaves, until finding one node satisfying OE,, SE (T) and then pull this node.
Followed path
06: 2 SE:
IV
The end-goal of the optimum-statistical collabora- tion is that, after pulling enough number of times, the following relationship holds along the shortest path from the root to the deepest node that contains the global maximum (If there are multiple global maximizers, the process only needs find one of them):
084
OEs SEs
OE SE 0E2 SE2
DE SEA
(2)
X
with slightly abused notation of SE to represent the uncertainty quantifier of the h-th node in the traverse path (refer to 2i In other words, the two terms collaborate on the optimization process so that SE is controlled by for cach node of the
Figure 2: Illustration of the optimun-statistical col- laboration framework. The node on the fifth level in the path will be pulled because its OE < SE
traverse path, and they both become smaller when the exploration algorithm goes deeper. Figure 2 illustrate the above dynamic process clearly with
5

---

Published in Transactions on Machine Learning Research (05/2023)
example tree on the standard partition. We remark that Equ. (2) only needs to be guaranteed the traverse path at each time instead of the whole exploration tree to avoid any waste of the budget. For the same purpose, all the proposed algorithms only require OE,, to be slightly larger than or equal to SE,, on each level.
We state the following theorem, which a general regret upper bound with respect to any choice of ( and OE and any design of the selection policy that follows the optimum statistical collaboration framework, with only a mild condition on the result of the policy in each round.
Theorem 3.1. (General Regret Bound) Suppose that under sequence of probability events {Er)t- 1,2,... 1.2." the policy (SS) ensures that at each time t, the node Phe,e pulled in line in Algorithm | satisfies f I (Tnhette S
max Meax(SER..) (S (T, OE I, where a >> 0 is an absolute constant. Then for any integer H e (n)) and any 0 < 6 < 1, we have the following bound on the cumulative regret with probability at least 6/(nn),
n
4n2
Rn, -
Σ ((E)) +
2n log
2aC
(EE 1
d
max (T,,) (t),
H(n)
SE (T,t)
H+1 (1))
where d d> d(a, C, 1),, d(a, -1) the near-optimality dimension w.r.l. a, C, and DE,-1-
Notice that in Theorem 3.1 we do not specify the form of DEn, (T,,;(T,t), t), or the specific selection policy of the algorithm. Therefore, our result is general and it can be applied to any function and partition that has a well defined d(a, C, -1 with resolution OE and any algorithm that satisfies the algorithmic framework. The requirement f- S a- max (SE de (T, t), OE } is mild and natural in the sense that it indicates the (SS) selects a "good" node to pull at each time t that is at least close to the optimum relatively with respect to OE or SE, with probability P(&)). Note that with a good choice of т, & can reduce to a subset of Ae, hence 1"=1 is bounded in L1. The terms that involve SE and QE are random due to H()), but can still be explicitly bounded when the they are well designed. Specific regret bounds for different choices of DE and a new SE are provided in the next section.
4 Implementation of Optimum-statistical Collaboration
Provided the optimum-stattistcal collaboration framework and its analysis, we discuss the some specific forms of the resolution descriptor and the uncertainty quantifier and elaborate the roles these definitions played in the optimization process. We then introduce novel VHCT algorithm based on one variance-adaptive choice of SE, which is a better quantifier of the statistical uncertainty.
4.1 The Resolution Descriptor (Definition
The resolution descriptor DE is often measured by the global local smoothness of the objective function (Azar et al., 2014 Grill et al. 2015). We first discuss the local smoothness assumption used by prior works and show its limitations, and then introduce a generalized local smoothness condition.
Local Smoothness. Grill et al. 2015) assumed that there exist two constants n > 0, E (0, s.t.
Yh 2 0, Vn E Phyy. f(x) 2 u
The above equation states that the function f is ssmoohh around the maximum at each level h. It has been considered in many prior works such as Shang et al. (2019); Bartlett et. al. (2019). The resolution descriptor is naturally taken to be OE,- = v1p
However, such a choice of local smoothness is too restrictive as it requires that the function and the partition P are both "well-behaved" so that the function value becomes exponentially closer to the optimum

---

Published in Transactions on Machine Learning Research (05/2023)
when as h increases. A simple counter-example is the function g(x)= 1 1/m defined on the domain [0, 1/e] with s(0) defined to be 0 (as shown in Figure [(b].. Under the standard binary partition, it is easily to prove that it doesn't satisfy Eqn. (3) for any given constants Po > 0, E (0,1). It might be possible to design a particular partition for g(z) such that Eqn. (3) holds. However, such a partition is defined in hindsight since one have no knowledge of the objective function before the optimization. Beyond the above example, it also easy to design other non-monotone difficut-to-optimizz functions that cannot be analyzed by prior works. It thus inspires to introduce a more general o(h)) smoothness condition for the objective to analyze functions and partitions that have different levels of local smoothness.
General Local Smoothness. Assume that there exists a function ((h): N - (0, 1] s.t.
wh 2 0, Vx E flx) 2 ((x))((1))
(GLS)
In the same example g(x) = 1+1/(Ixz)) it can be shown that g(x) satisfies Condition GLSS) with Φ(h) = 2/h Therefore, it fits in our framework by setting OE,, = 2/h and valid regret bound can be obtained for g(x) given properly chosen i since d(2, C, 1/h) < oo in this case (refer to details in Subsection 4.4) In general, we can simply set OE,- = (h) within the optimum-statiisical collaboration framework, and Theorem 3.1 can be utilized to analyze functions and partitions that satisfy Condition (GLS) with any <(h) such as (h) = 1/hP, for some p > 0 or even (h) = 1/(log h + 1); as long as the corresponding near-optimalityy dimension d(a, C, ((h)) finite for some a, C 0. Determining the class of smoothness functions d(h) that can generate nontrivial regret bounds would be an interesting future direction. Given such generalized definition and the general bound in Theorem 3.1
can provide the convergence analysis for much larger class of black-box objectives and partitions, beyond those that satisfy Eqn. (3.
4.2 The Uncertainty Quantifier (Definition 2
Tracking Statistics. To facilitate the design of SE, we first define the following tracking statistics. Trivially, the mean estimate (t) and the variance estimate (t) of the rewards at round t are computed as
(t,(tt)
1 Thie(t)
(t) (t,
Σ
x (Fn,),
(t) = (t)
Σ
(M())))) - (n.((t))
-Ran()))
The variance estimate is defined to be negative infinity when (() = 0 since variance is undefined in such cases. We now discuss two specific choices of SE.
Nonadaptive Quantificr (in HCT). Azar et al. (004)) proposed the uncortainty quantifier with the following form in their High Confidence Tree (HCT) algorithm:
(T,, bey log(A(())
((,;(1)
where b/2 is the bound of the error noise Et, A(t) max (01200000+///(( is increasing function of t, 6 is the confidence level, and c, C1 are two tuning constants. By Hoelfding's inequality, the above SE is a high-probability upper bound for the statistical uncertainty. Note that HCT is also special case of our OSC framework and its analysis can be done by following Theorem 3.1 In what follows, we propose an better algorithm with an improved uncertainty quantifier.
Variance Adaptive Quantifier (in VHCT). Based on our framework of the statistical collaboration, a tighter measure of the statistical uncertainty can boost the performance of the optimization algorithm, as the goal in Eqn. 2 can be reached faster. Motivated by prior works that use variance to improve the performance of multi-armed bandit algorithms Audibert et al. (2006 2009), we propose the following variance adaptive uncertainty quantifier, and naturally the VHCT algorithm in the next subscction, which is an adaptive variant of the SE in HCT.
2vn,((1 (()( 3bc log(A(())
SE (T.t) (T.t)= =
(4)
(t)
(t)
7

---

Published in Transactions on Machine Learning Research (05/2023)
Algorithm 2 VHCT Algorithm (Short Version)
Input:
known smoothness function @(h), partition P.
Run Algorithm with partition P and other required inputs as:
оЕ <(h), (T,,) Eqn.
44 ((S) pr.
The notations c, and (t) the same those in HCT. The uniqueness of the above (T, t) is that it utilizes the node-specified variance estimations, instead of a conservative trivial bound b. Therefore, the algorithm is able to adapt to different noises across nodes, and (T,, < ОE, is achieved faster at the small-noise nodes. This unique property grants VHCT an advantage over all existing non-adaptive algorithms.
4.3 Algorithm Example VHCT
Based on the proposed optimum-statistical collaboration framework and the novel adaptive (T, f), we propose a new algorithm VHCT as special case of Algorithm | and elaborate its capability to adapt to different noises. Algorithm provides the short version of the psendo-code and the complete algorithm is provided Appendix
The proposed VHCT, similar HCT, also maintains an upper-bound (t) for each node to decide collab- orative optimism. In particular, for any node Pr.i the upper-bound (t) is computed directly from the average observed reward for pulling TbZi
(t, = (t) + OE, + (T,,;
with (T, defined as in Equ. and OE, tuned by the input. Note that Un.((t) = co for unvisited nodes. To better utilize the tree structure in the algorithm, we also define the tighter upper bounds (t). Since the maximum upper bound of one node cannot be greater than the maximum of children, (b)
is defined be
(t, min Un,((t) max (Bx
5=0,1
The quantities (t) and (t) serve similar role of the upper confidence bound in UCB bandit algorithm Bubeck et al., (0111), and the selection policy (S) of VHCT is simply selecting the node with the highest (t) in the given set S, which shown in Algorithm 2 We prove that selection policy guarantees that (Thha)) I maxxxx(E,,,, (T,t), ) with high probability in Appendix as we required in Theorem
Follow the notation of Azar et al. 2014). define threshold value (t,s(t) for each node Pa.s to represent the minimal number of times it has been pulled, such that the algorithm can explore its children nodes, i.e.,
The (t) inf SE, (T, S DE, TEN
Only when Th (1) 2 The (l), we expand the search into Photi 's children. This notation helps to compare the exploration power of VHCT with HCT. Note that when the variances of the nodes are small, (T,, of VHCT would be inversely proportional to (t. and thus smaller than that of HCT. As a consequence, the thresholds (t) is smaller in VHCT than in HCT, and thus VHCT explores more efficiently in low noise regimes.
4.4 Regret Bound Examples
We now provide upper bounds on the expected cumulative regret of VHCT, which serve as instances of our general Theorem 3.1 when OE and SE are specified. Note that some technical adaptions are made obtain
L, bound for the regret. The regret bounds depend on the upper bound of variance history across all the nodes that have been pulled, meaning (a..0...17...0021 (t) Vmax for constant Vmax 0. Since
8

---

Published in Transactions on Machine Learning Research (05/2023)
the noise E is bounded, such notation is always well defined and bounded above. The Vmax represents our knowledge of the noise variance after searching and exploring the objective function, which can be more accurate than the trivial choice 6²/ /4, e.g., when the true noise is actually bounded by 6 for some unknown constant 8' < b. We focus on two choices of the local smoothness function in Condition GLS) and their corresponding near-optimal dimensions, i.e. ((h) = "2p² that matches previous analyses such as Grill el al. (2015); 0: Shang et al. (2019), and ((h) = 2/h, which is the local smoothness of the counter example Figure 1(b) For other choices of d(h), we believe similar regret upper bounds may be derived using Theorem 3.1
Theorem 4.1. Assume that the objective function f salisfies Condition
GLS) with ((h) vip" for two constonts 1/2 > P.. E (0. 1). The expected cumulative regret of Algorithm upper bounded by
Tن E S 22/2n logg(nn) + C1 V J (logn) गाা. + C2n 207 logn
14
where Ci and C2 are two constants and d1 is any constant satisfying di > d(3u1, C. Theorem 4.2. Assume that the objective function I satisfies Condition expected curulaaive regret of Algorithm 3 is upper bounded by
GLS with <(h) = 2/h. The
2uh 12 n 232 +3
2do
V B S 2/22 20mloo(4rr C1
12 max
(log 202+3 + C2n 2d243
log
where Oj and Oz are two constants and d2 is any constant satisfying d2 > d(2,c,1/h).
The proof of these theorems are provided in Appendix and Appendix D respectively. We first remark that the above regret bounds are actually loose because we do not a delicate individual control over the variances in different nodes. Instead, a much conservative analysis conducted.
In the literature, Grill et al. 2015 Shang et al. HCT are both +1 +2)))) when the objective function f satisfies Condition (GLS) with (hh = =1pp, while our regret bound in Theorem 4.1 is of order O(Vib/((+2)) (dd +))44) (log n) (((++)))) Although the two rates are the same with respect to the increasing of n, our result. explicitly connects the variance and the regret, implying a positive relationship between these two. Therefore, we expect the variance adaptive algorithu VHCT to converge faster than the non-adaptive algorithms such as HOO and HCT, when there is only low or moderate noise. The theoretical results of prior works rely on the smoothness assumption ((h) = viph,, thus are not able to deliver a regret analysis for functions and partitions with other ((h) (e.g. ((h) = 2/h in Theorem 4.2 Providing analysis for prior algorithms on functions and partitions with different smoothness assumptions is another interesting future direction to explore. However, we conjecture that VHCT should still outperform the non-adaptive algorithms in these cases since its SE is tighter measure of the statistical uncertainty. This thcoretical observation is also validated in our experiments.
2019 have proved that the cumulative regret bounds of HOO,
We emphasize that the near-optimality dimensions are defined with respect to different local smoothness functions in Theorem 4.1 and Theorem 4.2 Specifically, when the objective is piph-smooth, Theorem 4.1 holds even the number of ncar-optimal regions increase exponentially when the partition proceeds deeper, i.., when d(v1, C, p²) < xc. When the function is only 2/h-smooth, Theorem 4.2 holds only when the number of hear-optimal regions grows polynomially, i.c., when d(2, C, 1/h) < 0c.
5 Experiments
In this scction, we empirically compare the proposed VHCT algorithm with the existing anytime blackbox optimization algorithms, including T-HOO (the truncated version of HOO), HCT, POO, and PCT (POO HCT, (Shang et al. 2) and Bayesian Optimization algorithm BO (Frazier) 2018) to validate that the proposed varianco-adaptive uncertainty quantifier can make the convergence of VHCT faster than non-adaptive algo- rithms. We run every algorithm for 20 independent trials in each experiment and plot the average cumulative regret with 1-standard deviation error bounds. The experimental details and additional numerical results on other objectives are provided in Appendix
D
We use a noisy Garland function as the synthetic objective, which is a typical blackbox objective used by many works such as /Shang et al. (2019) and has multiple local minimums and thus very hard to optimize.
9

---

Published in Transactions on Machine Learning Research (05/2023)
VHCT
VHCT
VHCT
Cumulativv Regret
HOU
Cumulattin Begret
1-HD3
Cumulativv Regret
HDO
POO
POO
900
PCT
PCT
PCT
80
10e
222
821
Rounds
Rourds
Rounds
(a)
Garland
(b) Landmine
(c) MNIST
Figure 3: Cumulative regret of different algorithms on evaluating the Garland function and tuning hyperpa- rameters training SVM on Landmine data and neural networks on MNIST data.
For the real-life experiments, we use hyperparameter tuning of machine learning algorithms the blackbox objectives. We tune the RBF kernel and the L2 regularization parameters when training Support Vector Machine (SVM) on the Landmine dataset (Liu et al. (007), and the batch size, the learning rate, and the weight decay when training neural networks on the MNIST dataset (Deng) 2012). As shown in Figure 3 the new choice of SE makes VHCT the fastest algorithm among the existing ones. All the experimental results validate our theoretical claims in Section
6 Conclusions
The proposed optimum-statisticaal collaboration framework reveals and utilizes the fundamental interplay of resolution and uncertainty to design more general and efficient black-box optimization algorithms. Our analysis shows that dilferent regret guaranlees can be obtained for functions and partitions with different local smoothness assumptions, and algorithms that have different uncertainty quantifiers. Based on the framework, we show that functions that satisfy the general local smoothness property can be optimized and analyzed, which is a much larger class of functions compared with prior works. Also, we propose a new algorithm VHCT that can adapt to different noises and analyze performance under different assumptions of the smoothness of the function.
There still some limitations of work. For example, VHCT still needs the prior knowledge of the smoothness function ((h) to achieve its best performance. Also, the analyses in Theorem 4.1 and 4.2 are smoothhess-speeific.. Therefore, our framework also introduces many interesting future working directions, for example, (1) whether a unified regret upper bound for different ((h)-local smooth functions could be derived for one particular algorithm; (2) whether the regret bound obtained in Theorem
4.2 is minimax-
optimal for those ((h); (3) whether there exists an algorithm that is truly smoothness-ggnostic, i.c., does not need the smoothness property of the objective function.
References
Jean- Yves Audibert, Remi Munos, and Csaba Szepesvári. Use of variance estimation in the multi-armed bandit problem. 01 2006.
Jean- Yves Audibert, Rémi Munos, and Csaba Szepesvári. Expporation-exploitatinn tradeoff using variance ostimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876-1902, 2009.
Peter Auer, Ronald Ortner, and Csaba Szepesvári. Improved rates for the stochastic continum--rmeed bandit problem. In Nader H. Bshouty and Claudio Gentile (eds.), Conference on Learning Theory, pp. 454-468, 2007.
10

---

Published in Transactions on Machine Learning Research (05/2023)
Mohammad Gheshlaghi Azar, Alessandro Lazaric, and Emma Brunskill. Online stochastic optimization under correlated bandit. feedback. In International Conference on Machine Learning, pp. 1557-1565. PMLR, 2014.
Peter L. Bartlett, Victor Gabillon, and Michal Valko. A simple paramcter-free and adaptive approach to oplimization under & minimal local smoothness assumption. In 30th International Conference on Algorithmic Learning Theory, 2019.
Sébasticn Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in finitely-armed and contimuons-armed bandits. Theoretical Compuler Science, 412(19):1832 1852, 2011a.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12556):1655-166, 2011b.
Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillct. Foderated bayesian optimization via thompson sampling. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Newral Information. Processing Systems, volume 33, pp. 9687-96879 9699. Curran Associates, Tnc., 2020. URL https: pdf
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-1433 2012.
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, (1())27788 2806, 2015. doi: 10.1109/TIT.200 2405244955....
Peter I. Frazier. A tutorial on bayesian optimization, 2018. URL
1011/11177000111111
Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and D Sculley. Google vizier: A service for black-box optimization. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data miningg pp. 1487 1495, 2017.
Cean-Bastien Grill, Michal Valko, Remi Munos, and Remi Munos. Black- optimization of noisy functions with unknown smoothness. In Advances Neural Information Processing Systems. Curran Associates, Inc., 2015.
Kirthevasan Kandasany, Akshay Krishnamurthy, Jeff Schneider, and Barnabas Poczos. Parallelised bayesian optimisation via. thompson sampling. In Amos Storkey and Fernando Perez-Cruz (eds.), Proceedings of the First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 133-142. PMLR, 09-11 Apr 2018
Kenji Kawaguchi, Yu Maruyama, and Xiaoyu Zheng. Global continuous optimization with error bound and fast convergence. Journal of Artificial Intelligence Research, 56:153- 191153--9.... 2016.
Dragan Komljenovic, Darragi Messaoudi, Alain Cote, Mohamed Gaha, Luc Vouligny, Stephane Alaric, and Olivier Blancke. Asset management in electrical utilities in the context of business and operational com- plexity. In World Congress on Resilience, Reliability and Asset Management, 07 2019.
Lisha Li, Kevin Jamicson, Giulia DeSalvo, Afshin Rostamizadch, and Amect Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Reseavch, 18 (185):1-52, 2018.
Wenjie Li, Qifan Song, Jean Honorio, and Guang Lin. Federated x-armed bandit, 2022. URL https:
//axxiv. perxxvv.or/// httg//bb//22055/ 15268
Wenjie Li, Haoze Li, Jean Honorio, and Qifan Song. Pyxab a python library for armmd bandit and online blackbox optimization algorithms, 2023. URL httpt::t///// aaxxvvivv wttpv//rrr/aab//0..000000
11

---

Published in Transactions on Machine Learning Research (05/2023)
Qiuhua Liu, Xuejun Liao, and Lawrence Carin. Semi-supervised multitask learning. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Informalion Processing Systems, vol- wne 20. Curran Associates, Inc., 2007. URL http:://proceliigg.eerrrr petpr/pp..c/ppppe/////////L/
433aaf399b3330022330ef222233 Paper.pol
Odalric-Ambrym Maillard. Mathematics of statistical sequential decision making. PhD thesis, Université de Lille, Sciences et Technologies, 2019.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization.
arXiv preprinl or xxx:00907.,7740, 2009.
Rémi Munos. Optimistic optimization of a deterministic function without the knowledge of its smoothness. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148 175, 2016.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18, 07 2015.
Xuedong Shang, Emilie Kaufmann, and Michal Valko. General parallel optimization a without metric. Algorithmic Learning Theory, pp. 762-788, 2019.
Michal Valko, Alexandra Carpentier, and Rémi Munos. Stochastic simultaneous optimistic optimization.
In Proceedings of the 30th International Conference on Machine Learning, volume 28 Proceedings of Machine Learning Research, pp. 19 27. PMLR, 17 19 Jun 2013.
Chi-Hua Wang, Zhanyu Wang, Will Wei Sun, and Guang Cheng. Online regularization for high-dimensional dynamic pricing algorithms. arXic preprint arXiv:2007.02470, 2020.
ChiHua Wang, Wenjie Li, Guang Cheng, and Guang Lin. Federated online sparse decision making. ArXiu, abs/2202.13448, 2022.
12

---

Published in Transactions on Machine Learning Research (05/2023)
A Proof of the General Regret Bound in Theorem 3.1
Proof. We decompose the cumulative regret into two terms that depend on the high probability events {E Denote the simple regret at each iteration t to be A = f Tr, then we can perform the following regret decomposition
Rn
Σ 1=1
A
Σ [=
A,de,
+
Σ [=1
Aelles
R + R
< R
+
where we have denoted the first summation term in the second equality Σi=1 Alll, to R and the second summation term Ei= A,Te; to be R The last inequality because we have that both f and rt are bounded by [0, 1]. and thus A S. Now note that the instantancous regret A, can be written as
A = f² rt = p (Ihne))) + (Whiss) - r1 = Ahyn + A.
where we have denoted An.i = f (Im) and D = f (Dhent) - rt. It means that the regret under the events {E,)i= be decomposed into two terms Ry and Re.
22
R
It,
Aelle
A Mr.
A R + R
Note that by the definition of the sequence ) it is a bounded martingale difference sequence since E E[A, F--1= 0 and | < 1, where F, is defined to be the filtration generated up to time Therefore by Azuma's 's inequality this sequence, get
4n² 8
RC. <
2n log
with probability 1 5/(4n²). A even better bound can be obtained using the fact that A s 2 if < 2. However, RS not a dominating term and using b/2 only improves it terms of the multiplicative constant. Now the only term left is Re and we bound as follows.
H(n)
R
Ahai Te,
5
Σ
Σ
A (he
h=1
(f) t=1
H(n)
OSE (T.1)
Σ
Σ
Σ
oSE (T,()
h=1 (1)
H+1 ST x00) t=1
H
((n)
Σ
SE (T,t) + Σ
Σ
SE (T,t)
Am 5TT (1)
1=1
#11
(0) t=1
(II)
where H constant between and H(n) to be tuned later. The second incquality is because when we select. P Phojey we have SE (T,1) > OE,, by the Optimum-statisticaa Collaboration Framework. Also, under
13

---

Published in Transactions on Machine Learning Research (05/2023)
the event E,, have Ahr. I a max SEhe SEnii,,,,Ehh.. (T, The first term (I) can be bounded as
(1)
Σ
max SEA, (T, S In (m)) (a)
Σ
max (t)
SEA, (T,
k=
( t=1
h=1
t=1
<
21 (aDE
max (T,) (1)50
==1
H
(OE -
< 2aC'
max (T, (1)
h=1
where d > d(a C, -1 and d(a, -, is the near-optimality dimension with respect to (a, C, -I) The third inequality is because we only expand a node into two children, so [T)) S - (Note that do not have any requirements on the number of children of each node, so the binary tree argument here can be easily replaced by K-nary tree with K 2 2). Also since only select node (h, when its parent is already selected enough number of times such that OE 2 SE at particular time lo S n, we have Per 50 satisfies f - (( S a0E By the definition of (1. in the near-optimality dimension, we have
[x( ( s 2N, (10Ea-1)
and thus the final upper bound for (I). Therefore for any H E [1,, H()),, with probability at least 4n the cumulative regret is upper bounded by
R₂ = Σ
A
Se I(E)) + R
1=1
I v 2n log( 4n12/5)
+ Σ 1(89) + R
n
S / 2n log( (m 15) +
I(E 2aC
(DE 1)
max
(T,
H(n)
Σ
Σ
Σ
(
1 (1) t=1
B Notations and Useful Lemmas
B.1 Preliminary Notations
The notations here follow those in Shang et al. 2019 and Azar et al. (2014) except for those related to the node variance. These notations are ncoded for the proof of the main theorem.
At each time i, Phini denote the node selected by the algorithm where is the level and i, is the index.
Pt denotes the optimal-pant -ath selected at each iteration t
(t) denotes the maximum depth of the tree at time t.
(()) = 1/8((+) with /+ 2[1ogt/+1, 5(t) = min m1,
For any i > and h [1, (t). (t) denotes the set of all nodes at level h at time t.
14

---

Published in Transactions on Machine Learning Research (05/2023)
For any t > 0 and h E [1, (t) nodes (no leaves).
(t) denotes the subset of (t) that contains only the internal
Ca.i = (t E [1,]] Phosi = Ph,s} is the set of time steps when Ph. is selected.
Ct == Ch+1,25 U Uh+1121-11 the of time steps when the children of Ph are selected.
fns = m is the last time Ph. is selected.
Tu = max & is the last time when the children of Ph.s is selected.
IN = min {t: Tw,(tt) 2 Thii is the time when PA. is expanded.
(t)(tt) (T, Em (x*()))) (a.a) is the estimate of the variance of the Ph,s node time
Lg denotes all the nodes in the exploration tree time t
Vina is the upper bound on the node variance in the tree.
Note that if the variance of a node is zero, we can always pull one more round to make non-zero. Therefore, here we simply assume that the variance Vb,; is larger than a fixed small constant e for the clarity of proof, which will not affect our conclusions.
Algorithm VHCT Algorithm (Complete)
1: Input: Smoothness function o(h), partition P.
2: Initialize: T. = {Po.1. PP.1:PP.1.P:33 P1,2), (t) = U2,((t) = to0
for 1= n do
if ft then
for all nodes Ph,i Te do (t) mm,((t) + d(h) (T,,)
7: end for
8: PodateBackwwar((::.
9: end
10: Phide =PullUpdate(T:t (T,,t
11:
if The,i (t) 2 The (t) and Phr,i, is a leaf then
12: Te= To (Pr, +,22, -1, - 1,22,
13:
Un+1,2;(t) U 1 = to0
14: end if
15: end for
B.2 Useful Lemmas for the Proof of Theorem 4.1 and Theorem
The following lemma improves the results by Azar et al. (2014) and Shang al. 2019 Lemma B.1. We introduce the following event E,
2 (t) log (og(()(()))
3bc log log(1/8(tt) Th,
& vPh. C. (t), L.-.. ,t: (t). - (Dn s sov
Th (1)
where Tne E Phis is the arm corresponding to node Ph.s. If
c= 3 and 8(t) =
3t
then for any fived I, the event &, holds with probability at least 5/17.
15

---

Published in Transactions on Machine Learning Research (05/2023)
Algorithm 4 PullUpdate
1: Input: tree Tr, round
2: Initialize: (he, (.) = (0, S, = Po,1: Po,1;To,((t) ro(t) 1;
3: while Ph.re is not leaf, Th,,i (t) 2 Th (t) do
4: j j -00, 1B..
(h,, ic) = (1+ + 1, 24z - 5)
S, (Phmn
end while
Pull 2 and get reward Tt
Thi,i - (t) +1
10: Update Phnnd (t), Wenda (t)
11: Uni (1) = Phen i (1) + ((())
12: UpdateBackward (S,,t)
13: Return Ph..is
Algorithm UpdateBackward
1: Input: tree T, round
for Ph. backward from each leaf of T do if Ph,i is leaf of T then
(t, Ut,(t)
5: clse
7: end (t,((t) min (U), max, (Ba+122-,(()))
6:
Update the threshold (t)
end for
Proof. Again, L, denotes all the nodes in the tree. The probability of Ef can be bounded as
2 (g)(())))))
3be log( log(1/8(t))
P E < Σ
Σ
mnna 2 Vv [in.(t))
(h,((t) +
Th,(())
PA,tE Th,(t)=1
< Σ
Σ
3exp(-e2 log(-(())())())))
Er, (1)=
= 3 exxp(-c² log(1/6()) - |c,
where the second incquality is by taking c² log(1/8(1)) Lemma B.6 we have
2 (t) log(1/8(t))
3bc log(1/0((t)) (exp(-ooog(118(t)) (t)
P (f (xnx)) 2 V
(t)
Now note that the number of nodes in the tree is always (loosely) bounded by since we need at least one pull to expand a node, we know that
8
P 3 < (t)(
< 47
Lemma B.2. Given the parameters and ö(t) in Lemma hold is bounded as
B.1 the regret when the events {E,} fail to
Σ I(E)) S vn
t=1
with probability at least 1 (6n3)
16

---

Published in Transactions on Machine Learning Research (05/2023)
Proof. We first split the time horizon n in two phases: the first phase until vn and the rest. Thus the regret bound becomes
Σ I(E)) = >
((E))
Σ
I(EF)
t (-
The first (erm can be easily bounded by vū. Now we bound the second term by showing that the complement of the high-probability event hardly ever happens after t == vn. By Lemma B.1
8
P
Σ
P P
t
t
6n
v1+1
Therefore we arrive to the conclusion in the lemma.
Lemma B.3. At time under the event. &t, for the seleated node Phese and its parent (h²,"?) ??), we have the following set of inequalities for any choice of the local smoothness function o(h) in Algorithm
2V (t) (o))0g))/)( + 9bc² log(2/8(t))
1r (1 S 3//
Thi (t)
Th( (t)
= 30(h?)
Proof. Recall that Pe is the optimal path traversed. Let (W, Pt and (h","") be the node which immediately follows (h','') in P. (i.e., R²" = h1' 1). By the definition of B values, we have the following inequality
B S. max 1 Bw where the last equality is from the fact that the algorithm selects the child with the larger B value. By iterating along the inequality until the selected node (he, it) and its parent (h2, ll) we obtain
(t)
(h',2') Pt. BR (t) S Bri,t (t) S (t).s.t). A (1( E.P (l,,)), B (1) S (x S (1)
Thus for any node PA, E Pt, we have that (t) 2 (t),(t). Furthermore, since the root node (0, 1) is a an optimal node in the path P.. Therefore, there exists at least one node (h*,i*) E P. which includes the maximizer I' and has the the depth h² & hā < hy. Thus
Uniá (t) 2 Bu x (f), Ungz((t) 2 BRe, (t)
Note that by the definition of Un (t), under event E,
2 Nr (t) log((/01))
36c² log(L/ō(tt))
Unn.n (t) Then (f) ((h,) + Vv
The
The.s (t)
2T Ne (t) log(118((*))
3bc log( (og(1/5(tt)
< f( o(he) + +
(t)
Tha (t)
(5)
2 27 minee (t) log(1 1/((t)
3hc log(1/5(t)) 1/((t))
+ +CV
+ The
(t)
2 2Vni a (1) log(1/(((+t))
6bc2 ()((1))(1+))
$ {(hha))) + ((ht) + +20
(he
The (t)
where the first inequality holds by the definition of and the second one holds by 1 2 Similarly the parent node satisfies the above incquality
20,r x (1) log(1/0((+))
6bc² log(1 (og(1/((1+)) Tgg.o((1 (t)
(t) & f(mgg)) + +(()) 20
Top.2 (t) +
17

---

Published in Transactions on Machine Learning Research (05/2023)
By Lemma B.4 we know Un . (t) 2 f" If (*) is leaf, then by our definition B (t) Un (t) f" Otherwise, there exists leaf (hz, iz) containing the maximum point which has (h", (()) its ancestor. Therefore we know that f I Bhank I Bb s 80 B is always an upper bound for f Now we know that
2 h..h (t) log (1)g(((((+)) Thene (1)
6bc 6bc log(1/0(tt)) Thi (1)
f" S ((h,) + 2
2 nVng. NE.t (t) log(118((*))
6bc log log((18(t*t) (t)
- ((h)) 2
+
Recall that the algorithm selects a node only when The (t) < The,ie and thus the statistical uncertainty is large, i.e. ((hx) S S. (T, and the choice of Theike (t), we get
2V mani i (t) log(1/((tt))
9be log(1/8((*))
An.i (1) (1)5 S 30y
Thesi (1)
The (t)
2V Wnr (t) log(2/0(t)) This((() (1)
9be² log log(2/8(t))
S 3
Th
where used the fact ++ S 2t for any t. For the parent (k,, since st 2 (tg.e(() and thus ((P)) 2 SEap (T, (T,t), we know that
2 Ne. (1) log(1/8((t))
6bc loollog((11 log(1/8(t*)) 36()))
(t) o(h)) + 20,
The (t)
Thr (t)
The above inequality implies that the selected node Phin, must have 3x(h)) optimal parent under & O Lemma B.4. (U Upper Bounds f*) Under event Es, we have that for any optimal node (h",i*) and ony choice of the smoothness function <(h) in Algorithm 3 U (t) an upper bound on f*
Proof. The proof here is similar to that of Lemma 5 in Shang et al. 2019). Since 1 2 we have
2 . (1) log (1/((())))
3bc² log(1 (og(1/(tt+) The (t)
Uh (t) pi-- (f) + ((h)) + +
Th- (t)
2 s (t) (og((()()))
35c log(11 log(1/ō(tt) Th-, (t)
2 Mi,, i- (t) + ((h)) +Vy V
Th (t)
2 x(h))= + ff (x
where the last inequality is by the event Es,
2 (t) log (og((/(()) 3bc log log(1/8(t)) f(xw in (t) + +//
(t))
Th (1)
Lemma B.5. (Details for Solving T) For any choice of (h),, the solution Th,(l) to the equation ((h)
(T,,;(T,t) f) for the proposed VHCT algorithm in Section 4 is
3bō(h)
2
2
(t)
1
(n. (ogg0//1)))
(6)
(1)/2
20(h)²
Proof. First, we define the following variables for ease of notatioins
A o(h)
B = cv r. log(1/8((+))
C = 3be log(1 (/5(tt)))
18

---

Published in Transactions on Machine Learning Research (05/2023)
Therefore the original equation (hh) (T,t) can be written as,
A B (Ta,(!)
(h,s(t)
Note that the above a quadratic equation of (t), therefore we arrive at the solution
3bA
2 (l) log log(1/8((+))
(1, 1 1
(t)/
2A²
B.3 Supporting Lemmas
Lemma B.6. Let X X, be i. random variables taking their values in [p- 2.. 1+ 5l, where μ = [[ Let Xt, Ve be the mean and variance of (Xi) For any t N and 0, with probability at least 3e we have
2V
3hx +
t
Proof. This lemma follows the results in Lemma B.7
Note that X2, X2 E [u 2. + 2 we can
define Y, = X, (μ })) then Y,, .,,..., Y, E [0, b] and they are i.i.d variables. Therefore for any t N and
x >> 0, with probability at least 3e " we have
2V:(Y)²
3bx
Y
Since the variance of is the same as the variance of X, Therefore we have
|&, - 1l S 2Vx(X)x
+ 3br
Lemma B.7. (Bernstein Inequality, Theorem 1 in Audibert et al. (2009)) Let XI...., X4 be i. random variables laking their values [0, bJ. Let μ = E [(x)] be their commoon expected value. Consider the empirical mean X2 and variance defined respectively by
X, X and V Ei=1 (X, x.)
Then, for any t E N and x > O, with probability at least
3e x
2Vxx + l
36x
Xx 11 S
Furthermore, intvoducing
B(x,t) = inf <as3
log 1t) nt)e aa/a
logt
where u A denotes the minimum of u and v, have for any N and 0 with probability at least B(x,1)
2V.I 3br
[8 w| s
8
holds simullannoussyy for (1.2....,.)
19

---

Published in Transactions on Machine Learning Research (05/2023)
C Proof of Theorem 4.1
C.1 The choice of (t).
When ((h) = v1p", we have the following choice (t, by Lemma B.5
3
(t,
1
11ph (V),,, log(1/8(tt))
V h (t)/22
3b
3brrp"
c² llog (1/8(t))) (Vn,.(t)/2) P p-2h
2 2 2 1
(1)/2 (1,((1//2)
c² log (1/8 (l)( + v (1, + 6bv,, 2 (() 3b2rp")
p-2h
u2
Since variance non-negaaive, we have (t. 2 36e² p h When the variance term (ta is small, the other two lerms are small. We also have the following upper bound for (I))
(t, < D2 2 log (t))(,))
e² log (1/8 (t+)
2h + 36v1
o2
op
where we define the constant DJ = (Vmax + 2-2VV V2 max + 699 +66%max'1
(Vmax))
C.2
Main proof
This part of the proof follows Theorem later.
3.1
Let H be an integer that satisfies S H < H()) to be decided
(n)
<
Σ
tm1
4=0 (EIn.n) t=l
(m))
S 2aC
(DE,
max SE ta
Σ
SE (T,
SEIn(n)
1=1
1+ TET, t=
(a)
(6)
By Lemma B.3 we have a = 3 and thus the following inequality
RC < Σ
2Cp
(EIa(n) d(h-1) d(h-1 6c, 2( max (Tn, (onn)))))) 9bc log(2/5(m)) log( max (n)))
/
iEZn(n)
h=0
(a)
H(n)
Σ
Bey 2Th,, (n)V log22/0000 96c log(2/0((n..)) log (og
k= (m)
Now bound the two terms (a) and (b) of RC. separately.
20

---

Published in Transactions on Machine Learning Research (05/2023)
π (a) <
2Cp d(h-1)
60//
2( max (Tn, log(2/5(m)) + 9bc2 (og2log(2/((m)) log( max (Tn,((n))) VEIn(n)
iEZn(m)
h=0
77
ccp (gg(2/((n)) /cv 2V maxp h(d+1) + 20 /C3/3bccpp cp log(2/8(n)) 6CV 2V 2mxx 2mmaxpphlatt h(d+
<
"
4=0
+ 18Cp d(h- be log log(2/((n)) [log (log(2/8(m)) + 2 2
Dic -
2h 2
1/1
12 max
CD2c² m
log (20gg2222m)))) po
ldd+1) 12v6bu mmaxCee Cc2pp log(2/0(n)) ( -Id++
11 p)
11(1 - p)
18Cbe 1o (log (log(2/8(n))) + 2 log( (())
14
0 Hd
1-
+ 36C log(2/(())))) log( 2 (1-pay
piy ( 2 )p dH p2d)
where the second inequality we used the upper bound of (t) in Section B formula for the sum of geometric sequence and the following result.
The last inequality is by the
H
H-2
hp d(h-1) 1)
HP--(HH1)-
Hp
Σ dh h=-1
1 pr
h=0
(D -2 )
2²
p-d dH + 2d)
(1 جdp²
<
1
(p" - 2 p2d dH + p2d
(1 p)2
Next we bound the second term (b) in the summation. By the Cauchy-Schward Incquality,
(x))
(6o/22Th.(n)Waaa log(2/5(tn.))) + Idd log(2/8((h..)) log (m)s(n) }
(b) <
Σ
Σ
(n)
H(n)
((x)
Σ
Σ
log(2/0(tn.))) +
Σ
9bc²
1= (EI
(ZZ
Recall that our algorithm only selects node when (t) (t, for its parent, i.c. when the number of pulls is larger than the threshold and the algorithm finds the node by passing its parent. Therefore we have
Tai(Thas) 2 Ths(Fna). vh e [0. H()) - 1). E (n)*
So have the following set of inequalities.
21

---

Published in Transactions on Machine Learning Research (05/2023)
H(n)
H(n)-1
H(n)-1
H(n)-1
71 Σ
Σ
Tn,(nn) 2
Σ
Σ
Tns(n) 2
Σ
Σ
Th,elhndd) 2
Σ
Σ
0=0 inIn(n)
hm0
iE (m)
Am0
SETN (m)
A= iEz (m)
H(n)-1
2 Gog (1/ō(1+))
H(n) -1
log (1/8 (11
2 Σ
p 2h 2 pp-21 2
v2
vt
k=H
iET, (m)
h=
TEZz (n)
H(n)-1
log (1/8 max
1,2 t,
=e² p
2
29
h= H
iEz (m)
H(n)-1
max (1/8 (1 log (1/8 (f
= =pp 28
h= πf
iEZ, (m)
H (xx)-1
log (1/8 Tt ((h11.2611) 1) + +log (1/8( (Tt (Th+1.22))
2 p 2H
207
iET,, (n)
(n))
log (188 (F (th21-1)) + log (1/8 (F/22) (1122)
2pp-80 -28
Σ
Σ
2v7
1= 1EI (n)
2p 2H
((n)
Σ
log (1/8 (hh))
2v9
1= (EIa(n)
Note that in the second equality, we have used the definition of En,s, En.s = max(fr. En.s). Moreover, the third equality relies on the following fact
log (1/8 max (1 = max (log (1,8 (()11.2-1)) log (1/8 (2)
The next equality is just by change of variables h = + 1. In the last inequality, we used the fact that for any h 0, Ixt covers all the internal nodes at level h, so the set of the children of T (n) covers Th+1 (m). In other words, we have proved that
((m) Σ
2nx? 2H
Σ
log (1/5 (Fht))
<
c2e
h= +1 (EZn(n)
Therefore we have
(b) 2n PI evc
18b p2 log
+
If we let the dominating terms in (a) and (b) be equal, then
H (22/2V max (22/2VmixCDie Sep log(2/00 ai 20/n(1 p)
Substitute the above choice of nd into the original inequality, then the dominating terms in (a) and (b) reduce to Ö(C zoz n because Dj = θ(v V max,, where C₁ is a constant that does not depend on the variance. The non-dominating terms all Ö( 2245 we get
22

---

Published in Transactions on Machine Learning Research (05/2023)
R S (a) + (b) S Ci Va2i
" ) n2 --2 (log 5)
Can 2044 log
2011
(8)
where C2 is another constant. Finally, combining all the results in Theorem 3.1 Lemma obtain the upper bound
B.2
Eqn.
we
RVRCT
I vn + / Ingo + C1 Vi n тーン (log ") ) + C2n क0नन log
4n2
s 2 2n log(
4n²
_ + C2n log n + Ci Viaz n (log g )
The expectation in the theorem can be shown by directly taking ó 1/n in Theorem 3.1
D Proof of Theorem 4.2
D.1 Choice of the Threshold
By Lemma
B.5 we get that when <(h) = 1/h, we can solve for тa as follows.
1+ 1+ 3b/h
(t)
2 (V2(Vx.())())) log(1/o(tt))
(t)(()
(n,((t) + (t,((t)² 6b/hū, h, (t) 3b/h c² log (1/8 (t+))
s DIc log (1/8 (tt) h22 36c log
where we again define new constant Dj (Vimx + 2 V max 3bV max
6bV
O
D.2
Main Proof
The failing confidence interval part can easily done as in Section since &, also a bigb-trobability event each time We start from the bound on R By Thcorem 3.1 and similar what we have done Theorem 4.1 decompose Re over different depths. Let. H (n)) be integer to be decided later, then we have
((n)
R
Us. <
Σ
A de
t=1
h=0 (n) 1=1
H
((n)
< 2aC
[E 7
max SE,, (T,t) to (IIn(n)
Σ
SE (T,,)
h=1
(ETx t=1
(a)
(b)
Now we bound the two terms (a) and (b) of RC. separately. By Lemma B.3 have 3.
23

---

Published in Transactions on Machine Learning Research (05/2023)
H
(a) -
Σ
20h (60 2 /
l + 9bc Log(2/8(n)) log( max (x),(1)))) (EIn(m)
h=0
H
1e 1 /2log (n)) Vmmux log(2/(())))
h=0
h d+ $ / (1/6 (m)) Vmax log(2/0(m))
h=0
+ 18Cbe (olggg/((////) (2)(())) log (Dic² log (2/8 h²)
H
H
22 1+1 Log(2/og(()))))))) 2V max
Σ
3 (og(222++ /V 2V
h=0
h=0
H
18Cbe hd log(2/8(m)) log (Dfc² log (2)()))
k=0
H
< 12 12v 2V 1o
Σ nd+1 + 36bC (og22/()(())) 2V
h
d+
max
h=0
h=0
πf
+ loC log (Dic² log (2/8 (2)((m)) (n))
Σ hd
h=0
d+1
d+
< 12 12/21 2V m logee
Σ
+ 36bCc² log(2/0(m)) 2V 2V
Σ
H Σ h
18Cbe? (ogg2/(g) log (Dic² log (2/8 (n))
d+1
2+
< 12 2V 2 H(H + 1) 2
H(H + +1)
+ 36b6Cc² log(2/5(n)) (2
2
H
18Cbe 18Cbe> log((/6(()) log (Dic² log (2/8 (n))
Next bound the second term (b) in the summation. By the Cauchy-Schwarz Incquality,
(x))
(b) < Σ
Σ
6oy 2T (Th, log(2/8(Fn..)) + 96c log((//((h..))) Tha(n)
h= (m)
H (m)
H(x)
< n Σ
Σ log(2/5((n.)))
+
Σ
9b02
Ti
1= (M)
h= (ET,(m)
Recall that our algorithm only selects a node when (t) 2 (t) for its parent, i.. when the number of pulls larger than the threshold and the algorithm finds the node by passing parent.. Therefore we have
Ta.(Cha)) 2 (Ta))))) sh E [0, H(x) 1). E Ix)=
So have the following set of inequalities.
24

---

Published in Transactions on Machine Learning Research (05/2023)
H(n)
H(n)-1
H(n)
H(n]-1
Σ
Σ
Th,(nn)
Σ
Σ
Tha(n)
Σ
Σ
Tha(Tnas)
Σ
E
h=0 (n)
h=0
iE (n)
SEI, (n)
h=0
(n)
H(n)-1
H(n)-1 Σ
2 Σ
Σ
d² log (1/8 (+))) ch2 N H
log (1/8 1/8(F).)) ))
b==l
VET, (n)
h==
KEIn (m)
H(x)-1
=ee
Σ
Σ
log (1/8 (max(Tn-1122011 1,- [,+11,2] 1211))))
h==
(m)
H(n)-1
Σ
max{log (1/8 ((it122-1)) .log (118 (f1t1.2))
b=Tf
TEI (n)
H
2
H(n)-
E
log (1/8 Et (()11,2--1) + log (1/8 (2
2
h=иl
iET, (m)
((n)
Σ
Σ
log (1/8 ( (1h22-1)) + log (1/8 (1/0(th.z))
2
h TT
+1 iEI
((n)
Σ
log 1/8 (t.s))
2
h= (a)
Note that in the second equality, we have used the definition of Un = (ax( Moreover, the third equality relies on the following fact
log 1888 max (11412111 Fxt12)) ( = max log (1/8 (F log (1/8 (2
The next equality is just by change of variables h h + 1. In the last inequality, used the fact that for any h > 0, I (n) covers all the internal nodes at level h, so the set of the children of (n) covers T (m). In other words, we have proved that
H(n) Σ
log (1/8 (ft.)) S
2n 2 ccc
# (M)
Therefore we have the following inequality
2n
18bn log n
2
(b) < cve
H
H
If we let the dominating terms in (a) and (b) be equal, then
H' = (12 (12 max CD (elog(2/8(m))
2443
2n
Substitute the above choice of into the original inequality, then the dominating terms in (a) and (b) zd+2
reduce to Õ
where C1 is constant that does not depend on the max 2413 because D, = O(v max
2013
2011
variance. The non-dominating terms all ((12445) we get
25

---

Published in Transactions on Machine Learning Research (05/2023)
R S (a) + (b) S C1
V 2843 max
(log ") )ddis
+ Cyn 22
2d-1
log
π
(9)
where C2 is another constant. Finally, combining all the results in Theorem 3.1 can obtain the upper bound
Lemma
B.2
Eqn.
we
RyReT I vn + V 2n log(
4n
)
VVVx n 2643
2d+2 (log 8
n. )ddts + C2n 24-3 log
23-1
n 5
< 2 2n log(
4n²
C1 CiV.aae
42 Vmxx
2443 (log 8
2012
n 2d43 + C2n 20+3
2
n log
8
The expectation in the theorem can be shown by directly taking ò = 1/n as in Theorem 3.1
E Experiment Details
In this appendix, we provide more experiment details and additional experiments as supplement to Section 5 For the implementation of all the algorithms, utilize the publicly available code of POO and HOO the link https://rdrr http://ddrrri//rrarr./. Swran//OR/maa//////
html and the PyXAB library (Li et al. 2023 For all the we have used low-noise setting where e ~ Uniform (0mmm((0.085 -.005, 0.05)
experiments in Section 5 and Appendix E.2 E.2, to verify the advantage of VHCT.
E.1 Experimental Settings
Remarks on Bayesian Optimization Algorithm. For the implementation of the Bayesian Optimization which
algorithm BO, we have used the publicly available code at http:://githubb wwwwo///wweweeaeeeeeoooeoooaeeee is also recommended by Frazier (2018). For the acquisition function and the prior of BO, we have used the default choices in the aforementioned package. We emphasize that BO is much more computationally expensive compared with the other algorithms due to the high computational complexity Process. The other algorithms in this paper (HDO, HCT, VHCT, etc.) take at most minutes to reach the endpoint of every experiment, where as BO typically needs a few days finish. Moreover, the performance (cumulative regret) of BO not comparable with our algorithm.
Gaussian
Synthetic Experiments. In Figure 4 provide the performances of the different algorithms (VHCT, HCT, T-HOO) that need the smoothness parameters under different parameter settings {0.25, 0.5, 0.75). Here, we choose to plot an cquivalent notion, the average regret R,/t instead of the cumulative regret R, because some curves have very large cumulative regrets, so it would be hard to compare them with the other curves. In general, p = 0.75 or p = 0.5 are good choices for VHCT and HCT, and p = 0.25 is a good choice for T-HOO. Therefore, we use these parameter settings the real-life experiments and the additional experiments in the next subsection. For POO and PCT, we follow Grill et al. (2015) and use Pmax = 0.9. The unknown bound b is set to be b = for all the algorithms used in the experiments.
Landmine Dataset. The landmine dataset contains 29 landmine fields, with each field consisting of dif- ferent number of positions. Each position has some features extracted from radar images, and machine learning models (like SVM) are used to learn the features and detect whether a certain position has land- mine or not. The datasct is available at http::/www.. ee duke. hwt.eeeheel.aaaraaaannnnnneaaaae followed the open-source implementation
wtt.:/ooo//aaaa.e htap:chbbcccc//aaiiooogggna///ae zipp We have BBayesaan Optimization to process the data and train the SVM model. We tune two hyper-parameters when training SVM, the RBF kernel parameter from [0.01, 10), and the L2 regularization from [1c-4, 10). The model is trained on the training set with the selected hyper-parameter and then evaluated on the testing set. The testing AUC-ROC score is the blackbox objective to be optimized.
MNIST Datasct and Neural Network. The MNIST dataset can be downloaded from
lecun. , com/ exdp/mnist/ and one of the most famous image classification datasets. We have used stochas- tie gradient descent (SGD) to train a two-layer feed-forward neural network the training images, and the
26

---

Published in Transactions on Machine Learning Research (05/2023)
VHCT pm2.25
VHCT p.2.25
VHCT 0.25
64
p
64-
HCT p=225
66
HCT 0.25
Average negret
T-HOO 0=2.2
Average negret
T-HO0 p=2.
Avrerage Regret
T-HO0 p=
0.5
0.5.5
VHCT 0.5
HCTp=0:55
p=
HCT p
T-H
T-H00.p=0.3
T-HO0 p
VHCT 0.75
ViCCT.p=00755
VHCT p=
p
HCT p= 0.75
HCT p 0.75
T-HO0 p- 0.75
-HOO p 0.75
T-H00 p 0.75
3000
2000
2042
4000 5006
2000
2000
2000
4000
5006
2000
2000
2000
4000
5000
Rounds
Rounds
Rounds
(a) Garland
(b) DoubleSine
(c) 2D-Rastrigin
Figure 4: Best parameters on the Garland, DoubleSine and Rastrigin function
objective the validation accuracy on the testing images. We have used ReLU activation and the hidden layer has 64 units. We tune three different pyrameearameters of SGD to find the best hyper-parameter, specifically, the mini batch-size from [1, 100), the learning rate from [1e-6, 1], and the weight decay from [1e-6, 5e-1].
E.2
Additional Experiments
In this subsection, we provide additional experiments on some other nonconvex optimization evaluation benchmarks. They are used many optimization researches to evaluate the performance of different op- timization algorithms, including the convergence rate, the precision and the robustness such as Azar et al.] (2014); Shang et al. (2019); Bartlett et al. (2019). Detailed discussions of these functions can be found https:: //en. wwt.wikiipe www.iedia org/wiki/Test. functions for for_foorrrrrrrr optimization Although some of these function values (c.g., the Himmelblau function) are not bounded in [0, 1] on the domain we select, the convergence rate of different algorithms will not change as long as the function is uniformly bounded over its domain. To commit a fair comparison (i.e., sharing similar signal/noise noise ratio), we have re-scaled all the objectives listed below to be bounded by [_,,
We list the functions used and their mathematical expressions as follows.
(originally) a one dimensional function proposed by Grill et al. (2015 with multiple sharp local minimuns and one global minimum. The results are shown in Figure
DoubleSine (Figure [[a]
fx. v) = exp 1...200.5 + v2) + exp(0.5(cos 2nr + cos 2ny)] - c 20.
The counter example f(x) = 1 1/ / In in docreases too fast around zero and thus its smoothness cannol be measured by 1iph for any constants V1.P 0. However, because it continuously differentiable and even monotone, the function very easy optimize. The results are shown
Figure 6(b)
Himmelbalu (Figure 5(c) (originally) a two dimensional function with four flat global minimums. We use the negative of the original function for maximization, and we restrain æ be in [-5, 5)2 include all four global maximums. The results shown in Figure ((c)
f(z, v) = - + - 22+
Rastrigin (Figure 5(d) multi-dimensional function with a vast number of sharp local minimums and one global minimum. We the negative of the original function for maximization. We
27

---

Published in Transactions on Machine Learning Research (05/2023)
(a) DoubleSine
(b) Counter Example
(c) Himmelblau
(d) 10D-Rastrigin
Figure Plots of all the synthetic objectives used in the experiments. We have used a 10-dimensional Rastrigin function and the figure in (d) is Iwo-dimensional one.
VHSC
VISCT
VHCT
196
VHCC
MCT
Car wwwiddiieeeee Regiee
HDO
POO
Rounds
179
Rounds
Founds
386
Rounds
379
(a)
DoubleSine
(b) Counter Example
(c) Himmelblan
(d) 10D-Rastrigin
Figure 6: Cumulative regret of different algorithms on the synthetic functions.
all the algorithms on the 10-dimensional space [-1,1]10. The results are shown in Figure 6(d)
f(x)
-A + A cos (2Tx,)
x with A 10.
As can be observed in all the figures, VHCT is one of the fastest algorithms, which validates our claims in the theoretical analysis. We remark that Himmelblau is very smooth after the normalization by its maximum absolute value on |-5, 5J2 (890) and thus a relatively easier task compared with functions such as Rastrigin. DoubleSine contain many local optimunss that are very close the global optimum. Therefore, the regret differences between VHCT and HCT are expected be small in these two cases.
E.3 Performance of VHCT in the High-noise Setting
Apart: from the low-noise sotting, we have also examined the performance of VHCT the high-noise setting. In the following experiments, we have set the noise be e, Uniform(-0.5, 0.5)). Note that the function values in [-1,1], therefore such noise very high. As discussed in Section 4.4 it should be expected that the performance of VHCT is similar to only marginally better than HCT in this case, As shown in Figure 7 the performance of VHCT and HCT are similar, which matches our expectation.
28

---

Published in Transactions on Machine Learning Research (05/2023)
HCT
HET
230
HCT
HET
Camulesivve Regret
T400
Regret
Curnulesiss lesive Regret
POO
ICT
PCT
RCT
PCT
Curutertve
706
100
120
2001
(a) Garland
(b) DoubleSine
(c) Himmelblan
(d) 1D- Rastrigin
Figure 7: Performance different algorithms on the synthotic functions with high noise
29


Reviews:
[{"review_id": "ZuHiijayL7", "reviewer": "Reviewer_CwAy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In reviewing this paper, I believe its contribution to the field of black-box optimization is significant, as it provides a generic perspective of the balance between optimization error and statistical error and its algorithmic implications for a broader range of functions and partitions. The proposed algorithmic framework, optimum-statistical collaboration, does not rely on specific assumptions of optimization error and uncertainty estimates, and is believed to be applicable to a wider range of scenarios than previous works. The paper introduces a more relaxed assumption, known as General Local Smoothness, which can be applied to a broader range of objective functions than the assumption of Local Smoothness used in previous works. Theoretical analysis shows that VHCT has rate-optimal regret bounds under different local smoothness assumptions, while empirical results demonstrate its superior performance compared to prior methods. Overall, the article's novelty lies in the combination of multiple models and optimization algorithms within a statistical framework, leading to improved performance, as shown in the experimental results.\n\nThe paper's weaknesses include some sections lacking clarity, particularly in the introduction section, which could have been more concise and better structured. The technical terminology may also present challenges for readers unfamiliar with black-box optimization and related fields. Additionally, a potential limitation of the article is its assumption of reader familiarity with black-box optimization, which may pose difficulties for some nonexperts. Furthermore, while the experimental results are compelling, they are limited to a specific set of benchmark problems, and it would be helpful to see how the proposed approach performs on a wider range of problems.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a novel approach for black-box optimization that combines statistical modeling and optimization, called optimum-statistical collaboration. This algorithmic framework offers a more comprehensive analysis of the interaction between optimization and statistical errors during the optimization process, and is applicable to a broad range of functions and partitions that meet various local smoothness assumptions and different numbers of local optima. In addition, the paper introduces a variance-adaptive algorithm, VHCT, that outperforms prior methods in various settings. The proposed approach is designed to overcome the limitations of existing techniques for black-box optimization, which often rely on a specific model or optimization algorithm. The authors provide experimental results to demonstrate the effectiveness of their approach, showing that it outperforms existing techniques on a range of benchmark problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "One request for change is to offer more details on the specific models and optimization algorithms used in the experimental evaluation. This would enable readers to better understand the strengths and limitations of the individual components of the proposed approach. Additionally, including more discussion on the limitations of the proposed approach and potential future research directions would be valuable (for example, the introduction could be better structured to provide a clearer motivation for the research question and the proposed solution). Lastly, technical terms could be more explicitly defined, and more accessible language could be used where possible to improve the readability of the article. There are also other typographical errors that I would omit here for simplicity (but encourage you to do a thorough check).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GtrgfrJE1p", "reviewer": "Reviewer_JhQi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The results of Theorem 3.1 apply to examples for which existing methods do not work. Definitions 1 and 2 are more general than existing conditions.\n\n2. The idea of using Variance Adaptive Quantifier seems reasonable, and the VHCT algorithm achieves promising results.\n\n3. The paper is written in a clear and easy to follow way. Motivations are well presented using examples at the beginning part.\n\n**Weaknesses**\n\n1. The technical novelty seems limited. The major novelty of this work is using Eq. (4) as the uncertainty quantifier and the resulting VHCT algorithm. However, using variance in confidence interval seems an old existing idea in bandit literature, e.g., Eq. (4) is highly similar to existing UCB variants which use variances,\n\n[1] Exploration-exploitation trade-off using variance estimates in multi-armed bandits, Audibert et al., 2009.\n\n[2] Use of variance estimation in the multi-armed bandit problem, Audibert et al., 2006.\n\nGiven the studied problem of this work is highly related to bandit, I think the technical difficulty and novelty are limited.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the problem of black-box optimization, specially using hierarchical bandits-based algorithms.\n\nThe authors firstly define two general components, i.e., resolution descriptor (Definition 1) and uncertainty descriptor (Definition 2), based on which a general algorithm Optimum-Statistical Collaboration (OSC) is proposed, as shown in Algorithm 1.\n\nThe authors then prove a general regret upper bounds for OSC algorithm in Theorem 3.1. The results are general and they apply to examples in Figure 1, which satisfy general local smoothness assumption and finite near-optimality dimension but make some existing methods not work.\n\nIn Section 4, the authors propose to use Variance Adaptive Quantifier as the uncertainty quantifier in VHCT algorithm (Algorithm 2), which improves the existing HCT method of Azar et al. Theorems 4.1 and 4.2 show examples of regret upper bounds for the VHCT algorithm under different general local smoothness conditions.\n\nSection 5 shows experiments to compare the proposed VHCT algorithm with existing methods, including T-HOO, HCT, POO, PCT and BO, using synthetic objective functions such as Garland function, and hyperparameter tuning of machine learning methods (parameters of SVM and training neural networks on MNIST dataset). The proposed VHCT algorithm outperforms existing methods by achieving smaller cumulative regret.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Since my major concern is of the technical novelty of the proposed Variance Adaptive Quantifier and the resulting VHCT algorith,, I suggest discussing existing bandit literature of using variance in bonuses (such as UCB variants). The authors could comment on the difficulty and difference comparing with existing results, and this would help the audience better understand the contributions of this work. ", "broader_impact_concerns": "This work is mostly theoretical, and the experiments are conducted using public methods and datasets. There are no ethical implications of the work as I can see.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "m0gzhhQAOW", "reviewer": "Reviewer_np44", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper provides a general framework for bandit optimization of black box functions using a hierarchical search that includes general assumptions on the objective function (see Definition 1) and also on the statistical confidence intervals (see Definition 2). A relaxed assumption (General Local Smoothness) is then introduced that applied to a larger class of objective functions compared to the one in the existing work (Local Smoothness). \n\nAlthough the presentation is very clear and the general framework is interesting, I find the main contribution of the paper rather limited. In particular General Local Smoothness can be handled similar to Local Smoothness in the analysis. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers bandit optimization of a black box function using a hierarchical partitioning of the search domain. In this method, the search domain is partitioned into $2^h$ subdomains at each level $h$. Specifically, each subdomain in level $h$ is divided into two subdomains that form a binary tree with nodes representing the subdomains. The root represents the entire search domain. An algorithm then can be designed that traverses tree using statistical confidence intervals towards the optimum point of the objective functions. \nThe idea dates back to (Auer et al., 2007; Bubeck et al., 2011b) and has been studied in several other works. This papers contributes to the literature by relaxing the assumptions on the objective functions compared to the ones required in the existing work.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The term \"collaborative\" is used for the interplay between optimization error and statistical error. This may be a bit confusing as it may imply collaboration between multiple agents as common in the bandit literature. I would suggest changing this terminology. \n\nThe paper is overall very well written, there are however a few typos: \n\"Eqn.equation 2\" on page 5. \n\n\"To ensure the above probability requirement holds, it is reasonable to make $SE_{h,i}(T, t + 1) \\ge SE_{h,i}(T, t)$\" on page 5. Should the inequality be the other way around. I would expect the statistical error to decrease when more samples are collected. \n\n$g(0)=0$ on page 6 does not seem correct. ", "broader_impact_concerns": "As a mainly theoretical paper, this section seems not to apply. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript concerns the fundamental problem of black-box optimization. The authors consider a general class of optimization methods based on hierarchical partitioning (optimum-statistical collaboration) and analyze regret based on characterizations of the inherent resolution and uncertainty quantification mechanism.

The reviewers generally agree that the results in this paper are correct and of interest to a subset of the TMLR audience. There was some concern regarding the extent of novelty in the work; however, I judge the contributions to be of sufficient scope to warrant publication, and none of the reviewers stands in opposition to this recommendation.

Throughout the review and discussion period, the reviewers provided feedback and suggestions that the authors have faithfully incorporated into the manuscript. I believe these changes have strengthened the work.
Decision: Accept (poster)