Adaptive Partitioning Schemes for Optimistic Optimization
Authors: Raja Sunkara
Ardhendu Tripathy
Venue: ICML 2025 poster (2025)
Keywords: discrete optimization
derivative-free optimization
black-box function
regret bounds
subspace learning
neural networks
surrogate modeling
Primary area: optimization->zeroorder_and_blackbox_optimization

Abstract: Applications such as engineering design often require us to optimize a black-box function, i.e., a system whose inner processing is not analytically known and whose gradients are not available. Practitioners often have a fixed budget for the number of function evaluations and the performance of an optimization algorithm is measured by its simple regret. In this paper, we study the class of ``Optimistic Optimization'' algorithms for black-box optimization that use a partitioning scheme for the domain. We develop algorithms that learn a good partitioning scheme and use flexible surrogate models such as neural networks in the optimization procedure. For multi-index functions on an $m$-dimensional subspace within $d$ dimensions, our algorithm attains $\tilde{O}(n^{-\beta / d})$ regret, where $\beta = 1 + \frac{d-m}{2m-1}$, as opposed to $\tilde{O}(n^{-1/d})$ for SequOOL, a state-of-the-art optimistic optimization algorithm. Our approach is competitive across a wide range of numerical benchmarks. Additionally, we introduce weight quantization in a large language model as a novel task for black-box optimization. Our approach improves the quality of Activation-aware Weight Quantization (AWQ) of the OPT-1.3B model, achieving an approximate 10\% improvement in performance relative to the best possible unquantized model.

Adaptive Partitioning Schemes for Optimistic Optimization
Raja Sunkara Ardhendu Tripathy?
Abstract
function. Additionally, an axis-aligned rectangle scheme limits the application to low-dimensional search spaces (as the number of rectangles grows as kddn, where k is the num- ber of splits at each height, d is the dimension and n is the number of splits needed in each dimension), or it may fail to exploit low-dimensional structures in high-dimensional spaces. Thus, there a need to develop partitioning schemes that can adapt to the low dimensional structure that may be present in a black-box function.
Applications such as engineering design often re- quire to optimize a black-box function, i.e., system whose inner processing is not analyti- cally known and whose gradients are not avail- able. Practitioners often have a fixed budget for the number of function evaluations and the per- formance of an optimization algorithm is mea- sured by its simple regret. In this paper, we study the class of "Optimistic Optimization" algorithms for black-box optimization that use partitioning scheme for the domain. We develop algorithms that learn a good partitioning scheme and use flex- ible surrogate models such as neural networks in the optimization procedure. For multi-inde func- tions on an m-dimensional subspace within d di- mensions, our algorithm attains O(n-//d) regret, where 3 1+ 2m-I. as opposed 0(n-1/d) for SequOOL, state-of-the-an optimistic optimiza- tion algorithm. We use our approach to improve the quality of Activation-aware Weight Quantiza- tion (AWQ) of the OPT-1.3B model, achieving ~ 10% improvement in performance relative to the best possible unquantized model.
Global optimization is impossible without restricting the class of functions: degenerate function that takes the value at particular location and zero everywhere else can only be optimized by sampling every point in the domain. The class of functions typically restricted by assumptions on its "smoothness". One of the first global optimization algo- rithms with provable convergence of Lipschitz functions. The DiRect algorithm (Jones et al., 1993; Jones & Martins, 2021) is well-known algorithm that can optimize Lipschitz functions without knowing the Lipschitz constant. A different class of functions studied in the Bayesian Optimization literature is that of the Gaussian Process (GP) prior for the unknown function f. Combining the observed samples with the prior mean and covariance kernel, posterior distribution for ʃ is obtained and used to guide the sampling strategy, see e.g. GP-UCB (Srinivas et al., 2012). Since its sampling strategy required maximiz- ing the Upper Confidence Bound obtained from the poste- rior, its could feasibly be applied only on low-dimensional X. Later works (Shekhar & Javidi, 2018; Salgia et al., 2021) incorporated domain partitioning ideas to reduce the com- putational cost. GP- can also be applied if belongs to a Reproducing Kernel Hilbert Space corresponding to the covariance kernel. However, these methods require the kernel associated with f as an input.
obtained for the class
1. INTRODUCTION AND MOTIVATION
Optimization of black-box functions is often carried out by a class of algorithms called "Optimistic Optimization" algo- rithms (Munos, 2014). These algorithms are preferred due to their mild assumptions; however, they require a partition scheme to be provided for the search space. The quality of partitioning scheme depends on the function being opti- mized (Grill al., 2015). If information on the function is lacking, then a default partitioning scheme, i.c., axis-aligned rectangles, is used (Jones et al., 1993; Bartlett et al., 2019). But this default choice might not be a good choice for the
Unlike the above methods, which assume global character- istic for f. the "Optimistic Optimization" class of algorithms (HOO (Bubeck et al., 2011) 1). SOO (Munos, 201 1). SequOOL (Bartlett et al., 2019)) just assume local smoothness con- dition around the global maximizer. This local smoothness ensures that the function does not rapidly decrease around its maximum value. These algorithms require as input a hier- archical partitioning of X' that is well-behaved with respect to semi-metric on X. Although the semi-metric is not needed to be known, the performance of these algorithms
Misssurri University of Science & Technology, Rolla MO, US "OpsCanvas. Alexandria VA, US. Correspondence to: Raja Sunkara <rs5eq@mst.cdu>> Ardhendu Tripathy <ard- hendu hendu@opscanvas.c @owseeaossssoos.......
Proceedings of the 4 International Conference on Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Adaptive Partitioning Schemes for Optimistic Optimization
can be heavily influenced by the choice of the partitioning scheme. Absent any additional information, the default par- titioning is the axis-aligned rectangles from DiRect, leading to the shortcomings described in the beginning. We propose to develop an algorithm that adaptively builds a partitioning scheme as new samples are collected. Additionally, it refines partitions using SequOOL in the low dimensional subspace that accounts for most of the variation in the function.
to the low-dimensional subspace dimension, which is dif- ficult to obtain in real-world problems. Additionally, the Bayesian Optimization algorithms can be computationally expensive for large budgets.
Latent Action Monte Carlo Tree Search (LA-MCTS) (Wang et al., 2020) recursively partitions the high-dimensional search space into regions with high/low function values using nonlinear decision boundaries. It serves as a meta- algorithm by using existing black-box optimizers (e.g.. BO, TuRBO (Eriksson et al., 2019)) as its local model. LA-MCTS creates sub-regions by partitioning the variable ranges without reducing dimensionality. Each sub-region retains the full dimensionality of the original problem space. While LA-MCTS has shown good empirical performance, it encounters challenges in high-dimensional spaces. Voronoi Optimistic Optimization (VOO) (Kim et al., 2020) is method for optimizing functions in high-ddmensional spaces. Instead of using fixed partitions, VOO creates flexible sec- tions called Voronoi cells. Each cell contains points closest to a specific evaluated point. As new points are evaluated, the cells automatically adjust based on the best results.
We sumarize the main contributions of our paper below.
We demonstrate the benefit of using learned partition- ing scheme for existing derivative-free optimization algorithms such as SequOOL.
When the function is a low-dimensional multi-index function we theoretically prove improved regret bounds shown in Table
Empirically, we demonstrate the improvement in opti- mization error for several benchmark functions includ- ing Rastrigin (multi-modal), Branin (multiple minima), and Sharp Ridge (non-differentiabbe).
We pose the quantization of Large Language Model (LLM) as a tigh-dimensional black-box optimization problem and obtain an improved perplexity value.
Evolutionary algorithms such as CMA-ES (Hansen, 2023) and simulated annealing (Xiang et al., 2013) are other popu- lar approaches for black-box optimization. The CMA-ES technique performs well in finding the best solutions in high-dimensional optimization problems. However, these methods do not have convergence guarantees (Loshchilov & Hutter, 2016; Nomura al., 2021).
SOO pvn
SequOOL ((6)
Our Method p pai()
1
0 =
7>0
0 Ó(n 1//)
Ō(n
Ö(n-8/0
2. PROBLEM SETUP & ADAPTIVE PARTITIONING SCHEMES
Table Regret bounds on a budget of n evaluations for a m- dimensional multi-index function in d dimensions. B == 1+ d-m. and p, 17 are parameters for the default partitioning scheme.
2m-T
We consider the problem of optimizing function f: X + R using only its evaluations at appropriately chosen points in its domain X, which is assumed to be a closed and compact set. Given budget of evaluations, at each t E (1. n the algorithm queries a point x, E X' and observes a real number y/- = f(x:). After exhausting its budget, the algorithm returns the estimated maximizer (n).. The optimization error is quantified by the simple regret rn, defined as
Related works Here we summarize the methods we have compared in our experiments. Perhaps the closest related work is Random Embedding Simultaneous Optimistic Opti- mization (RESOO) (Qian & Yu, 2016), which scales SOO to high-dimensional optimization problems by applying SOO in random low-dimensional search space. The simple re- gret of RESOO depends only on the effective dimension of the problem, rather than the full dimension of the solution space. REMBO (Random EMbedding Bayesian Optimiza- tion) (Wang et al., 2016) uses a random projection matrix to create dimee--dimeiii embedding for high-dimensional optimization problems. It then applies Bayesian optimiza- tion on this now-dimensional space, allowing efficiently search for optima in the reduced space. HeSBO (Nayebi et al., 2019) uses hashing-enhancee embeding subspaces. ALEBO (Adaptive Linear Embedding Bayesian Optimiza- tion) (Letham et al., 2020) builds upon and improves the original REMBO by proposing a new lincar-ebeeddingg method. However, these algorithms requires an lower-bound
rn 2 fr f(((n)), where f & sup f(x), xEX
and x" X' such that f = f(x)).
Our focus is on the class of optimistic optimization algo- rithms (Munos, 2011; Bubeck et al., 2011; Valko et al., 2013; Munos, 2014; Grill et al., 2015; Bartlett et al., 2019). These algorithms require as input a hierarchical partitioning of the domain X for their search procedure.
Definition 2.1. Partitioning scheme (Bartlett et al., 2019). Let P denote a tree representation of the domain X. All the
2

---

Adaptive Partitioning Schemes for Optimistic Optimization
A=
Degth & I: wai triection
index i, the cell A,,s - {A E Th.s) J is cell in the partitioning on the m-dimennional projection of X onto the subspace spanned by rows of A.
Since the projection of X onto A can result in points outside X. the value of is chosen to ensure that the projection is covered by the A partitioning scheme. An appropriate value of is in the following definition.
[A]
Definition 2.4. Let Cj E (-1,1) denote the 2 corners, indexed by J. of the default axis-aligned p partitioning scheme. Given matrix A with m orthonormal rows de- noted as a1, ag, ams we define
Depiht trancction
Deptis
Leiaccion
O'max
max a Ojr max ag Cj: ... max a Cz 151524 15J524
13/524
as the extent the A partitioning scheme. We choose the largest component of the extent
(4)
max,, a, cy.
A blte rxpeessuts cell that cissectdd at loiggtt
An orange dot represcats cell that not trisected at height
In this paper, we will provably demonstrate the advantage of our method when there is oiw-dimensiona ridge structure present in the black-box function. We consider the class of multi-indee functions (Fornasier et al., 2012), i.c., there is matrix A E g with orthonormal rows and Lipschitz function g such that
Figure 1. First four depths of the default partitioning P on [-1,]]]]]] 1]a
cells at depth h form a partition of X' and are denoted as Ph- We index the cells at depth h with an additional index i, i.e., Ph, is cell in the tree depth A cell Pa,s partitioned obtain one or more cells of Ph++1 Px denotes cell at depth h containing maximizer x* of f and Xn, denotes representative location within the Ph,s cell.
f(x) = 9(Ax).
(I)
Then optimizing over the low-dimensional subspace is suf- ficient recover the maximizer. All proofs and omitted details can be found in the supplementary.
A common choice for the domain is obtained when have interval constraints each of its components. In this case, without loss of generality, we can consider X' = [-1, 1] And a default choice for the partitioning scheme that is often used in practice is the axis-aligned trisection scheme (Jones al., 1993). We use HIT" to denote the unit hypercube in m-dimensional space. i.e., [- 1] domain.
multi-index function with f(x g(Ax). xfx* E EX= [-1, is an optimizer and a is chosen per definition 2.4, then there is x Th such that s(A (ATzz) 2²) = f(xx) and || S a.
Proposition 2.5. Suppose f Rdd +>
Proof Sketch. For an optimizer x" E [-1, let z Ax*. Then f(A T 2²') f(A Ax") = f(x'(( since A A is identity. We then use that x* lies in convex hull of cube corners and apply the definition of to show that I 1l I a, see details in Appendix 11.4.
Definition 2.2. The default partitioning scheme P {Pr,i h ] of [-1, 1jdd uses axis-aligned trisection method in round-robin manner (see Figure 1). At depth h = 0, there is a single cell Po,1 X. Each cell Ph., at depth h split into three children cells Ph+1,, at depth h++1. The trisection occurs along the (h mod d) + axis, i.e., the new cells are created by introducing (d dimeensional hyperplanes orthogonal the chosen axis. For all h, the representative X4,; ; is the midpoint of the cell Ph.i.
The above proposition implies that if we have access to the true subspace matrix A, we can compute and restrict our optimization to the m dimensional space aHy using the A partitioning scheme. We theoretically characterize the benefit of using the partitioning scheme AA for the class of multi-index functions, i.e., satisties (1) then using the partitioning scheme A can decrease Tn, at faster rate with To show this, we use the partitioning scheme assumption made by Grill et al. (2015) and Bartlett et al. (2019) that states that the suboptimality of any point in the Pj cell improves as depth h increases. The rate this improvement is characterized by parameter E (0, 1).
We consider partitioning schemes that not aligned with the standard axes. We define such a rotated low-dimensional partitioning scheme using matrix of orthonormal rows.
Definition 2.3. Given A E gd such that AA In and a scalar a > O, we establish a partitioning scheme denoted as A. Let the default partitioning scheme (Defini- tion 2.2) on [-a, ax" m be denoted T. For any depth h and
3

---

Adaptive Partitioning Schemes for Optimistic Optimization
Assumption 2.6. (Bartlett al., 2019) For any global op- timum x", there is a > 0 and p (0, 1) such that for all h E No and all x E Pi we have that fx) 2 f(x*) up"..
Algorithm Obtaining directions for an adaptive partition- ing scheme
Require:
T. oracle for f which is a multi-index function defined using A (see (1))
Bartlett et al. (2019) define the near-optimality dimension which characterizes the difficulty of optimizing a black-box function using partitioning scheme.
I: Sample ʃ at 7 points chosen as 2:10 sid (O, and fit single hidden-layer neural network ø
2: A + top right singular vectors of the hidden layer weight matrix preserving 95% variance
Definition 2.7. (Bartlett et al., 2019). Consider a partition- ing P that satisfies Assumption 2.6 for some v, p. For any C >>> 1, the near-optimality dimension hp (V, p. C) of f with respect to the partitioning P defined as
3: a t- Upper bound to dist. (A, A) obtained in
Lemma 9.11 or Theorem 9.12
4: return Å and á (see Equation 4) used to specify the partitioning scheme A in Definition 2.3
1p TV, ps C) A in 2 0: (Wr(3rp)) S Cp 4h 2 0},
where (3up")) is the set of near-optimal cells Pa,s at depth h for which s f(x)= 2 f(x") 3xp".
|11|- - 2 is 1yp = 0.5. For the partitioning scheme A from Definition 2.3 with A I2, a = 1 and direction selec- tion strategy th. 1 h mod A 0 and Th. 2 otherwise. its near-optimality dimension 77,4 0.
Intuitively, a larger P implies that the function is only im- proving slowly near the maximizer, and a larger 7 implies that there many near-optimal cells which must be ruled out to get the true maximizer. In both cases, we need larger budget of evaluations to converge. The following example shows a partitioning scheme A with a lower near-optimality dimension than the default partitioning scheme.
Empirically, we increase the optimization budget, we observe that SequOOI. on A decreases regret at faster rate than SequOOL on d for the above example functions.
Example 2.8. Consider the function f(11, x2) = g(Ax)=
3. PROPOSED ALGORITHMS FOR BLACK-BOX OPTIMIZATION
1 1- | with A = [1, 0] and g(2) = - |z]. Let 1yp, VIA be the mpar-optimalliy dimensions for the partitioning schemes P, A defined in Definitions 2.2 and 2.3, respectively.
To utilize an adaptive partitioning scheme, we develop two kinds of algorithms: 1. a two-stage algorithm where the first stage learns an adaptive partitioning scheme and the second stage uses it for optimization, and 2. an interleaved algo- rithm where learning and optimization happen iteratively.
Then we have that пp and 7A4 0.
In the next example, the subspace defined by A is not aligned with the canonical axes and we see that PA is smaller than p of the default partitioning scheme.
Example 2.9. Consider the function f(11, 9(Ax)
Two-stage algorithm. In the first stage, we use learning algorithm to obtain A, i.e., the directions used to define the adaptive partitioning scheme A. If f is a multi-index func- tion satisfying (1), the quality of this estimate is measured by the subspace distance between À and the true A. The value of å chosen in Lemma 4.5 is such that f f(A t) = fxx) for some t E [-á, 6mm and the optimization can find the maximizer in the low-dimensional subspace.
1- [2] + x22 with A- = [1, 1] and g(k) = 1- - [k]. Let WP,, VLA be the near-optimality dimensions for the partition- ing schemes P, A associated with (v, p). (V., Pa) respec- tively. Then = 1/v3 and PA = 1/3 and 7pp = 7 = 0.
In addition to identifying the important subspace spanned by m orthonormal directions, an adaptive partitioning scheme can choose which direction to split at each depth.
Definition 2.10. Direction selection strategy. For par- titioning A in Definition 2.3, a direction selection strat- m] defined for each height h takes the history H of all past function evaluations till depth h - and outputs the index of the direction to be split at depth h.
Algorithm learns À by fitting a single hidden-layer layer neural network to the function evaluations at random locations in its domain. A single hidden-layer neural network can model the fact that only a subspace of the domain explains all the variation in the function values (see Proposition 8.,.. In practice, we can choose the value of m to explain a desired percentage (such as 95%) of the total variation in the SVD step calculating Á. Another approach to learn Á is from Fornasier et al. (2012, Algorithm 2) which estimates the gradient of the function using finite differences. The second stage applics SequOOL to the partitioning scheme A returned by Algorithm 1.
egy Th: H + [1
In the following example, a direction selection strategy that splits the æ axis twice as often as the T2 axis results in a lower near-optimality dimension than that of the default partition P which splits both the axes in equal proportion. Example 2.11. The optiaalty dimension of the de- fault partitioning scheme for the function f(11, x2) =
4

---

Adaptive Partitioning Schemes for Optimistic Optimization
tionships between three partitioning schemes: the default Require: Total number of openings n, number of samples T for updating S. integer stating how often f is updated, number of dimensions m, oracle for f. direction selection strategy Th-
Algorithm 2 SequOOL on an adaptive partitioning scheme with direction selection strategy
scheme P. the scheme A based on the true subspace A, and the scheme A based on the estimated subspace A. Our analysis proceeds in two main stages: We first relate the parameters of the default partitioning scheme P to those of the scheme A. This includes comparing their SequOOL parameters (v,P), p). characterizing their star cells, and bound- ing the number of near-optimal cells. We then extend this analysis to the estimated scheme A, relating its properties to those of A. This involves quantifying the impact of using an estimated subspace and establishing relationships between the SequOOL parameters of Á and A.
Setup partitioning scheme A with A and á obtained by (Fornasier et al., 2012, Algorithm 2)
Obtain f by fitting a neural network on available samples, set max < [n²/ (nlogn + 30)
for + 1 to fmax do
Th < the cell with the largest function sample value at height h
We will use the notation of lattices to relate the number of near-optimal cells in two different partitioning schemes.
if h mod c= 0 then
Obtain evaluations of f at T' uniform random loca- tions in Th and update f
Definition 4.1. (Vaikuntanathan, 2011) Given m lin- early independent vectors bj..... bn E R the lat- tice generated by them is defined as L(b bm) (E a;b; ag E Z) We call b1,--.; bnn a basis of the lattice. We denote lattices formed by the standard basis vec- tors C1, e2,..... Cm as A. Thus, A = L(e1, .2.....
end if
Open [ cells at depth and trisect them along the direction returned by Ti (f)
end for
return x(() & arg maxall h, (xh.s)
.e......m... cm) = zm. The lattice A scaled by a scalar is is the same as L [(ke,, ( kez....
Interleaved learning and optimization. Instead of sepa- rating the learning and optimization in two distinct stages, an interleaved algorithm updates the neural network fit at regular intervals. The updated approximant is used to spec- ify the direction selection strategy in Definition 2.10.
For a d-dimennional vector x = (2i,-..,Iad T we use |x||, and ||x||.c to denote its lp and &oo norm respectively. The following lemma bounds the number of cells from a finer partitioning scheme that cover a given region in the domain.
Lemma 4.2. Let K. K E R+ with > Rt, and let B(x, r) (y E Rm : lly- xI S Sr.. Consider a lattice A as defined in Definition 4.1, scaled by kt, and translated by vector t to form the lattice A + t. Define the subset of all lattice points that cover (00, K) as C(n, n.,t) S. A t, i.e.,
Algorithm 2 uses a parameter Th that takes the updated approximation f as input. Our proposed method for Th is the lookahead direction selection strategy, which is detailed in Algorithm 3 in Appendix section 3.
A different value of Nmma is used in Algorithm 2, com-
E C(H,K', = {co E tt: B(c,, (B((0x)) #0
n² used in SequOOI., to account for the additional evaluations required to update the surrogate model f at regular intervals. This adjustment ensures that the total number of evaluations, including both SequOOL openings and model updates, remains within the overall bud- get. The following proposition guarantees that the chosen fmax ensures the total number of function evaluations does not exceed 3n.
pared to /mmax = nlogo]
and B(O,x) S SU BBC,, R')}
Then, the cardinality Cf satisfies:
16 KJ
< CCC,, n/, t)l S k²
+
We switch from A to T to simplify analysis by working di- rectly in the low-dimensional space. Detailed mathematical justification is in Appendix Section 11.13.
Proposition 3.1. Let n. T, T,C, lmaa be the parameters de- fined in Algorithm 2 with logn e "i= 1. :. Then the total number of function evaluations laken by the algorithm will not exceed 3n
The following lemma provides upper bound on the num- ber of near-optimal cells in scheme A relative to scheme P. This relationship is fundamental for comparing the near- optimality dimensions of the two schemes, which will be addressed in a subsequent lemma (Lemma 4.4).
4. THEORETICAL ANALYSIS
We show that for the class of multi-index functions (I), the partitioning A obtained using the learned À can have a lower and a lower p compared to that of the default partitioning P. Our proof proceeds by analyzing the rela-
Lemma 4.3. For the partitioning schemes P and 'T from Definition 2.7, let Np(e) be the number of cells Phas at depth h for which supxePa. f(x) Z f(x*) - c, and similarly for
5

---

Adaptive Partitioning Schemes for Optimistic Optimization
(e)()). Then
A
NT(() S CNp(e) where C= 3 (12
d = 2
Vi-disMAAA)
A
X 1-1.1"
Proof Sketch. Consider the following POpl relation:
(0.0)
Aup
Tan
POpt A {(Th,s, Pho): Thi E (e)(e), Pau E No(e),
sin dist(A, A]
Th AAph, #0}.
APh. A {Ax Phsht
Ät
opie
V/ (A.A)
171
The segment denotes the image of The under the map resulting Ane-
For any h, consider the cell This E (e). Let be the lower hound to the number of elements in POpt that are of the form (Th,s: -), implying |POpt| 2 [NT(e)) Similarly, for any h.j. consider the cell Ph., E (c). Let be the upper bound the number of elements in POpl that are of
Figure 2. Illustration of Lemma 4.5 for d = 2, m = 1, showing the truc subspace A and the estimated subspace Å used in defining the expansion factor.
the form (., Ph.j). Then, we have: [Np(e)] 2 [POpt].
We previously computed p p= 1/v3 and PA = 1/3, which confirms the first conclusion. Additionally, since both tp and 17,4 are O, the second conclusion holds with equality.
Combining these two inequalities, we get:
[W+(e) s (Wr(e)) u
(2)
When the low rank matrix A is unknown, we use the esti- mation guarantees for the learning algorithms of Fornasier et al. (2012) and Mousavi-Hossehie et al. (2023) that bound the subspace distance dist (A, A). The subspace distance between the two row subspaces A and Å and is given by A ATAl,, where ||-1|2 denotes the spectral norm.
In our proof in Appendix 11,10, we further refine the upper bound on u to (12 m (dd () and the lower bound on / to (1/d)d-mgh (oddmmghhe (3 leading to the result.
The above lemma is a key technical result that enables us to
relate the parameters of the partitioning schemes A and P.
The following lemma shows that need an upper bound the subspace distance dist A, A) to ensure that opti- mizer exists within the low-dimensional search space.
Lemma 4.4. For a function in the multi-inde index class (1)
with known A E Tgmxd and m < d, let (v, P. tpp, C),
(PA,PA, (PA, PA, MA, CA) be parameters of P.A. Let ls 2 l
inf te fxx). Then we have that
Lemma 4.5. Consider
multi-indes function f(x)
(Ax) over IRd. Let x" be an optimizer of J within 1]4 a be as in definition 2.4 and Å be an estimate of A satisfy- ing dist (A, A) < 1. Then there exists a z² E I such that A(A z f(xx) and ||2" S
VA = max(v. v. 1p (1mmmmmm
PA = p²:
v/m
nA(KA.PA, CA) S 7p (V, P, C3/B,
V1- (A.A)
a.
and CA = 3d get o--m m (12v/m) mo ha
Proof Sketch. Consider a z" satisfying AA x = Ax". Since dist(A, A) < 1, the matrix AA is invertible, giving that z = (AA )- 'Axx and f(A T z²) = g(AA z²) =
where& 3 2 1+ d-m
2m-1 2m.1h hy a flogs Ki and
K1 2 3[log vmaa]
he -
log,
V
gAA (AÅ ) Axx) = f(x*). Finally, we bound 2 I1 using matrix norm inequalities and the subspace distance (A,A) A) in Appendix 11.12.
Proof Sketch. Lemma 9.4 shows that A is a valid partition- ing scheme and relates its parameters to those of the default partitioning scheme P. We then use Lemma 4.3 to bound the number of near-optimal cells in A, see details in Ap- pendix 11 11.
Figure 2 shows an illustration of the lemma. Specifically, optimizing f over the blue segment is enough to obtain its optimum value over X = [-1, 1J2. The value of & used in Algorithm is obtained from this lemma. If we have a u > dist A, A), then since a vd, we set
0
Since 3 2 1, the previous lemma shows that 7 S Tp. Fur- thermore, since p E (0, 1). PA $ p and S V/A. As an illus- tration, Example 2.9 satisfies the conditions of Lemma 4.4 d-m = 2. This with d = 2, m = 1, and hence 3 = =1+ 2m-1
á A v dm/ (1 u2)
(4)
implies P.A = p² and (MA, PA: CA) S (v C2/2.
to ensure is larger than
a. The value of
v V1-dista (A.A)
6

---

Adaptive Partitioning Schemes for Optimistic Optimization
is obtained from Lemma 9.11 or Theorem 9.12, along with Lemma 9.8. In practice, m is chosen to obtain A that preserves 95% variance in the hidden layer weight matrix.
(vr Shz p
1p 0,
In -
(v, (lv p)p--ha
-Bha
Pp
111p 0,
The next lemma bounds the number of near-optimal cells in If in terms of those in T. This is a key step toward compar- ing their near-optimality dimensions (see Lemma 4.7).
log A
where 7(u, p) = max max (e, 0) 1m- ,19).
Lemma 4.6. For the partitioning schemes T and I in Definition 2.3, let No (3uTp4) be the number cells This at depth h for which su...TT.. g(z)= Z f -3 Similarly, let Nz(33707, be the number of cells Tuis at depth for which su.z 9(AA 2) 2 f - -3u Then
G = 3dd
mm Cp no-noo ar ppopo and
[n/logn| 1pp log(1/ p) /C/,,
with h2 m m
logs wa-1
h1 = d [logs v /mal and where ha, has are from equations (3)
2ymnx
m
K2 V1 dist and (6) respectively.
dist? (A.A)
20 (4(3440)) S 4tH (33UTpT)
When pp > O, Algorithm has rn = (1+ O1+ 1/mp) while default SequOOL would give showing our approach reduces the regret at faster rate. The proof of this theorem follows from ap- plying the SequOOL parameters derived in Corollary 9.7 to Theorem 5 of Bartlett et al. (2019). Detailed proof is in Appendix 11.20.
=
Proof Sketch. We aim to upper-bound the number of near- optimal cells in the partitioning scheme T in terms of those in T. The key idea is to relate the two schemes through the transformation AÅ under which we optimize the function
(AA 2) over T. For a near-optimal cell Thi E T. its preimage under this transformation defines a bounded set B in Rm, which enclose within hypercube of computable size. To bound the number of near-optimal cells in T, we count how many of its cells at height h can intersect this hypercube. We invoke the Lemma 4.2 and show that at most 4th such cells can intersect the enlarged region. The complete proof is provided in Appendix 11.17
5. EXPERIMENTS
All implementation details, benchmark functions, and experiment scripts can be found at our GitHub repos- itory: ttw.rrrttiiiiistsseseeoooooo
com/ ra camm/raaa-sunie ju-suaaaaa//
Searned-Partitioon
Lemma 4.7. Consider the partitioning scheme Å obtained using A. Let l = g* infzergoRy g(AA z). Then,
We evaluate our algorithms against baselines from various optimization categories. These include Bayesian Optimiza- tion (REMBO (Wang et al., 2016), HesBO (Nayebi et al., 2019)), Evolutionary Algorithms (CMA-ES (Hansen et al., 2003)), Dual Annealing (Pincus, 1970), Optimistic Opti- mization (SOO, SequOOI, RESOO (Qian & Yu, 2016), DiRect), and Random Search. The optimization functions used in our experiments include Sphere, Rastrigin, Different Powers, Rosenbrock. Styblinski-Tang Hartmann-6, Branin, Ellipsoid, Sharp Ridge, and the CUSTOM function defined as 141++0 (z) 1111-117) 1)2 Ei=d-m+2(1; - 1)
" PAA PA-PA 7 S ST A
with
- CA p nahs h2 m +
logs
2 mmni
K22
162 =
m
h4 =
V logpA V.A
(6)
V dist? (A, A)
In our experimental setup, we construct the multi-index function as f(x) (Ax), where x E RR g RT + R is a standard optimization test function, and A E Roxd is a randomly generated matrix satisfying AA = Im- The Branin and Hartmann-6 functions are defined in 2 and 6 dimensions respectively; thus, we choose m = for Branin and m for Hartmann-6 when constructing the multi-index function. To further evaluate the efficacy of our algorithm, we conducted benchmarks on low-dimensional multi-index functions with d = 5 and m = 2. Additional experimental results are in Appendix 12.2.
Proof Sketch. We first relate the SequOOL parameters (v, p) of the partitioning scheme A to the scheme A us- ing Lemma 9.6, yielding expressions for (A). Next, using the bound on the number of near-optimal cells in A (Definition 2.7), we upper bound the number of near-optimal cells in À by composing with the Lemma 4.6. The complete proof is provided in Appendix 11.18
Theorem 4.8. For a function in the multi-index class (I), the regret of SequOOL applied on the partition- ing scheme using A returned by Algorithu and à
Our algorithm demonstrates superior performance on the Rastrigin, Sphere and Styblinski-Tani functions, achieving
vdm/ dist? (A, A) satisfies
7

---

Adaptive Partitioning Schemes for Optimistic Optimization
+ (4g
Rastrigin-72d
10%
Regret
Regret
10-1
10-5
10-10
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1580
1750
2000
Sphere Rotated-72d
Different Powers-72d
10a
Regret
10
Regret
10:2.
10-*
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Rosenbrock-27 72d
Styblinskl-Tang-722
10a
10-1_
Regret
Regret
10-2-
10-6.
10"1
10-11
250
500
750
1000
1250
1500
1750 2000
250
500
750
1000
1250
1500
1750
2000
Hartmann-6- 6-
Branin-72d
10-1__
Regret
10a
Regret
10-1-
10-11-
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Ellipsoid-72d
Sharp Ridge-72d
10a
10'
Regret
Regret
10-1
10-2
10-1
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Direct
SequOOL
Dual Annaaling
RESOO
HESBO
500
CMA-E5
SequOOL
Random Search
Figure 3. Regret Plots: Algorithm (SequOOL. on A) uses 650 additional samples to learn the subspace. Regret is plotted for 100 equally spaced budget values hetween and 2000. For the randomized algorithms, we took 10 trials and plotted the median curve (thick line) and 0 and 95 percentile curves. Random Search is run on A.
zero regret with fewer samples compared other methods.
5.1. LLM Quantization
On the different powers function, we perform comparable to the other methods, however, on the (x1 - 1)² + (I72 1)a, Ellipsoid and Sharp Ridge function, our algorithm perform slightly worse than the RESOO. This may be attributed to
The AWQ (Lin al., 2024) method for quantizing large language models formulates optimization problem as:
a" = arg min C(s e<
the use of several (650) samples for the first stage 2000 budgeted experiment.
C(s) = ||@(W-sw@)))) ss - X) - WX
Where X is the input features to the block which is cached from calibration dataset. It uses the parameterization sx. where Sx is the activation scale computed from X and a E [0. 1] and Q as the quantization function and W as the original weights (full pell--peciisoo). To determine the optimal a², AWQ applies a 1D grid search over the interval
8

---

Adaptive Partitioning Schemes for Optimistic Optimization
[0, 1]. This parameter controls the scale of activations and influences quantization error.
Table 2. L.M Quantization Experiment Results
Algorithm
Compute
WikiText-2
Calibration
Each layer of the LLM contains three primary components: the attention matrices (W2, W w and w all four matrices share a single a per layer), the first fully connected layer (W one a per layer), and the second fully con- nected layer (Wf :one per layer). Consequently, this leads to three optimization parameters per layer, resulting in total of 3M parameters to optimize across M layers. Each of these parameters is derived from separate optimization problems, all of which are solved through the grid search method in the interval [0, 1] to find the optimal value of a".
Time
PPL
-Set PPL
Grid Search
23 9 hours
16,92
14.62
SequOOL
2J 10 hours
16.83
14.28
Algorithm
2 10 hours
16.96
14.42
Algorithm 2 hours
16.68
14.29
tion by relating the near-optimality dimensions of different partitioning schemes for the same function, Empirically, we observe that our proposed approach is better or comparable to existing methods over wide range of benchmark func- tions and can be applied to high-dimensional functions. For example, the Rastrigin function, SequOOL achieved regret of 4.22 x 10-5, while our method reached zero regret. Against RESOO, on both the Rastrigin and Styblinski-Tame functions, our method achieved zero regret compared to 5.5 x 10-3 for RESOO on Rastrigin. For Styblinski-Tane our method reached zero regret with approximately 900 evaluations, versus 2000 for RESOO.
We propose a new approach which involves solving this LLM Quantization as high-dimensional black-box optimiza- tion problem. In our approach, we jointly optimize all layers to minimize perplexity: So, approach has one optimiza- tion problem in 3M dimensional space, compared to AWQ which has 3M one-dimensional optimization problems. Let represent the scales for all M layers,
a = [a.,...,,a3.. with each layer having three parameters. We define our proposed optimization problem as:
Some limitations of our approach estimating the low- dimensional subspace dimension and using an upper bound on the subspace distance in our algorithm. When the multi index assumption is not valid, we see only a mild benefit over SequOOI., e.g., in the AWQ experiments, our proposed objective function has function variation in all the directions and improvement over SequOOL is minimal. In the two- stage algorithm, the first stage chooses samples randomly for the subspace learning and these samples reduce the budget available for optimization.
a = arg min PPL(a) 1888
Where, PPL(a) is the perplexity on the calibration set after quantization using the scaling factors derived from a.
We evaluated our approach on the OPT-1.3B model (Zhang et al., 2022), with results presented in Table 2. Our pro- posed objective function using SequOOI. over 72 dimen- sions outperformed AWQ, achieving lower perplexity on both WikiText-2 (Merity al., 2016) and the calibration set (Pile dataset (Gao et al., 2020)). More details are in Appendix 12.3.
There are several avenues for future work. We can extend our approach to the case when the function evaluations are noisy. We can consider other low-dimensional functions be- yond the class of multi-index functions, e-g., functions with bounded second order variation in the Radon domain (Parhi & Nowak, 2022). Obtaining theoretical guarantees for di- rection selection strategy could be possible using active learning techniques, e.g., in (Mukherjee et al., 2022).
To quantify this improvement, we compare perplexity scores across methods. The perplexity of the unquantized model is 14.47, which we treat as a reference point for comparison. Quantization with the AWQ baseline increases perplexity to 16.92, resulting in perplexity gap of 2.45. In contrast, our proposed method (Algorithm 2) achieves perplexity of 16.68, reducing the gap to 2.21. This corresponds to relative improvement of approximately 10% in perplexity degradation compared to AWQ, demonstrating the benefit of jointly optimizing the scaling factors across all layers.
6. DISCUSSION AND CONCLUSION
We have proposed an adaptive approach to learning a good partitioning scheme for black-box optimization. When the function belongs to multi-index class, we prove that the adaptive partitioning scheme results in lower regret. To achieve this, we have developed a novel theoretical contribu-

---

Adaptive Partitioning Schemes for Optimistic Optimization
Acknowledgements
Hansen, N. The ema evolution strategy: A tutorial, 2023.
URL htw.s: http::///axxvvvo/e haagg//b//// 604 00772.
This material based upon work supported by the Na- tional Science Foundation under Grant No. 2246187. The authors thank the reviewers and meta-reviewers for their careful reading and insightful suggestions, which signifi- cantly improved the quality of the paper. Ardhendu Tripathy acknowledges the helpful discussions with Robert Nowak.
Hansen, N., Müller, S. D., and Koumoutsakos, P. Reduc- ing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (ema-es). Evo-
lutionary computation, 11(1):1-18, 2003.
Jones, and Martins, J. The direct algorithm: 25 years later. Journal of global optimization, 79(3):521- 566, 2021.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Jones, R., Perttunen, C. D.D and Stuckman, E. Lips- chitzian optimization without the lipschitz constant. Jour- nal of optimization Theory and Applications, 79:157-181, 1993.
Kim, B., Lee, K., Lim, S., Kaelbling, L., and Lozano-Péree T. Monte carlo tree search in continuous spaces using voronoi optimistic optimization with regret bounds. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 34, pp. 9916-9924, 2020.
References
Bartlett, P. L.., Gabillon, V., and Valko, M. A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption. In Garivier, A. and Kale, S. (eds.), Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learn- ing Research, pp. 184-206. PMLR, 22-24 Mar 2019. URL http:t/::/// httpp/proceenng.../ce mlr. w.lrrpon www.mml......//p..m. press/v98/ bartlett19a.he
Letham, B., Calandra, R., Rai, A., and Bakshy, E. Re-examining linear embeddings for high-dimensional bayesian optimization. Advances in neural information processing systems, 33: 13:1546-1558, 2020.
Lin, J., Tang, J., Tang, H., Yang, S., Chen, W.-M., Wang, W.-C., Xiao, G., Dang, X., Gan, C., and Han, S. Awq: Activation-aware weight quantization for on-device Ilm compression and acceleration. Proceedings of Machine Learning and Systems, 6:87-100, 2024.
Bubeck, S., Munos, R., Stoltz, G., and Szepesvári, C. X- armed bandits. Journal of Machine Learning Research, 12(5), 2011.
Chen, Y., Chi, Y., Fan, J., Ma, C., et al. Spectral methods for data science: statistical perspective. Foundations and Trends@ in Machine Learning, 14(5):566-806, 2021.
Loshchilov, I. and Hutter, F. Cma-es for hyperparameter optimization of deep neural networks. arXiv preprint arXiv:1604.07266 2016.
Eriksson, D., Pearce, M., Gardner, J., Turner, R. D., and Poloczek, M. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. arXiv preprint 1609.0600.078// 2016.
Mousavi-Hosseini, A., Park, S., Girotti, M., Mitliagkas, I., and Erdogdu, M. A. Neural networks efficiently learn low- dimensional representations with SGD. The Eleventh International Conference on Learning Representations, 2023. URL https: http::://pppeeevveeeee net forum? i id=6taykzgcPD.
Formasier, M., Schnass, K., and Vybiral, J. Learning func- tions of few arbitrary linear parameters in high dimen- sions. Foundations of Computational Mathematics, 12: 229-262, 2012.
Gao, L., Biderman, S., Black, S., Golding, L.. Hoppe, T., Foster, C., Phang, J., He, H., Thite, A., Nabeshima, N., et al. The pile: An 800gb dataset of diverse text for language modeling, arXiv preprint arXiv:2101.00027, 2020.
Mukherjee, S., Tripathy, A. S., and Nowak, R. Cher- noff sampling for active testing and extension ac- tive regression. In Camps-Valls, G., Ruiz, F. R.. and Valera, I. (eds.), Proceedings of The 25th Interna- tional Conference Artificial Intelligence and Statis- tics, volume 151 of Proceedings of Machine Learn- ing Research, pp. 7332-7432. PMLR, 28-30 Mar 2022. URL http://pccceeen..eeee/// mlr .press/ #151/mukherjee222e html.
Grill, J.-B., Valko, M., and Munos, R. Black-box opti- mization of noisy functions with unknown smoothness. Advances in Neural Information Processing Systems, 28, 2015.
10

---

Adaptive Partitioning Schemes for Optimistic Optimization
Munos, R. Optimistic optimization of deterministic func- tion without the knowledge of its smoothness. Advances in neural information processing systems, 24, 2011.
Wang. L.,, Fonseca, R., and Tian, Y. Learning search space partition for black-box optimization using monte carlo tree search. Advances in Neural Information Processing Systems, 33:19511 1199511-19522 2020.
Munos, R. From bandits monte-carlo tree search: The optimistic principle applied to optimization and plan- ning. Foundations and Trends in Machine Learn- ing, 7(1):1-129, 2014. ISSN 1935-8237. doi: 10. 1561/2200000038. URL 1561/2200000038
Wang. Z. Hutter, F., Zoghi, M., Matheson, D., and De Feitas, N. Bayesian optimization in billion dimen- sions via random embeddings. Journal of Artificial Intel- ligence Research, 55:361-387. 2016.
Xiang, Y., Gubian, S., Suomela, B., and Hoeng, Gener- alized simulated annealing for global optimization: the gensa package. R J., 5(1):13, 2013.
Nayebi, A., Munteanu, A., and Poloczek, M. A framework for bayesian optimization in embedded subspaces. In International Conference on Machine Learning, pp. 4752- 4761. PMLR, 2019.
Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M.. Li, X., Lin, X. V., al. Opt: Open pre-trained transformer language models. arXiv preprint 2rX:v:2205.01000000 2022.
Nomura, M.. Watanabe, Akimoto, Y., Ozaki, Y., and Onishi, M. Warm starting cma-es for hyperparameter optimization. In Proceedings of the AAAI conference artificial intelligence, volume 35, pp. 9188-9196 2021.
Parhi, R. and Nowak, R. D. Near-minimax optimal estima- tion with shallow relu neural networks. IEEE Transac- tions on Information Theory, 69(2): 125- 1140, 2022.
Pincus, M. A monte carlo method for the approximate solu- tion of certain types of constrained optimization problems. Operations research, ((66):2255112 1970.
Qian, H. and Yu, Y. Scaling simultaneous optimistic opti- mization for high-dimensional non-convex functions with low effective dimensions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Salgia, S., Vakili, S., and Zhao, Q. domain- shrinking based bayesian optimization algorithm with order- optimal regret performance. Advances in Neural Infor- mation Processing Systems, 34:28836-28847 2021.
Shekhar, S. and Javidi, T. Gaussian process bandits with adaptive discretization. Electronic Journal of Statistics, 12(2):3829-332 2018.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. W. information-theoreli regret bounds for gaussian process optimization in the bandit setting. IEEE transactions information theory, 58(5):3250-3265 2012.
Vaikuntanathan, V. Csc 2414 lattices in computer science.
mit wtw.l..miteed... eduu /tccl//couRsEES//C2241111 [Online; accessed 19-July-0008).
pdf,, 2011.
Valko, M., Carpentier, A., and Munos, R. Stochastic simul- taneous optimistic optimization. In International Confer- ence on Machine Learning, pp. 19-27. PMLR, 2013.

---

Adaptive Partitioning Schemes for Optimistic Optimization
7. Notation
Let No = INN (0) denote the set of non-negative integers and [d] represents the set (1,2,.... .d]. For vectors and matrices, we use (-)T denote the transpose. For a d-dimensional vector x = [T),..., ...,,.'''' we use ||x||p and ||x|| to denote its lp and lo norm respectively. For any matrix X = [x,..... x,], | 2| and |X F represent its spectral and Frobenius norms. We use (X) for the 1th largest singular value, with max (X) and miin (X) denoting the largest and smallest singular values. Suppose A E Rmmxd with AA = Im. then for any vector E Rd, we denote its orthogonal projection onto the span of the rows of A as VII A Av, with the orthogonal component given by V1 = V - VII. For a matrix W E Rpxd, we denote Wii || and W1 T as the projections applied each row, i... Wi = WA A and WT W WWI- For a given scalar 6 > O, we denote k.Y' as the set {no x E )) By a partitioning scheme P with K, we mean the domain for the partitioning scheme is the set {Na: x E [-1, By the default partitioning scheme P. we mean partitioning scheme P h
with A = 1. To describe side-length of a hyper-rectangle, we use the notation
[3-
mm
This expressions represents
1=1-
a vector of m components, where each component is given by 3- Aitmi J, with i ranging from to m.
8. Omitted details for Section 3
A single hidden layer neural network with p hidden neurons maps input E Rd to the scalar
Ú(x W, W. a)
Σ as (w] x + bz):
(7)
where a is the non-linear activation function, W is the hidden layer weight matrix consisting of p weight vectors denoted as Wg. by is the scalar bias for the ith hidden neuron, and og are the components of the output layer weight vector. The following proposition shows that the class of single hidden layer neural networks can represent the important subspace of multi-index functions.
Proposition 8.1. Consider a function [(x) = =i= no x + bi), where x E Red and a is a non-linear function.
Let x Px + (I P)x. where P is the projection matrix that maps any x E R to Span (W1, W2,..., W Wp). Then f(x) = E'_1 (wo Px + b.). And if x E Bdd are such that (x (xxx') 1 Span[w1, W2...., wp), then f(x) = f(x').
We use SGD with weight decay to fit the neural network on the function evaluations obtained at uniform random locations in X. The top yn right singular vectors of the learned weight matrix of the hidden layer is used as the estimated A for obtaining the partitioning scheme A.
Algorithm describes our lookahead direction selection strategy Th (f).
Querying outside the domain and optimizing f In practice, with our optimization domain set as X' = [-1, 1]d, we may encounter situations during low-dimensional subspace optimization where t E [-a,a] results in Á t & X. To ensure that f can be evaluated in all cases, we employ a two-step approach. First, we attempt to solve the optimization T subject Å t + Å, t. E X, where Å consists of the remaining d - m columns
problem: arg min,,. A T
tc
of À that are not in Å. If this optimization problem has no feasible solution, we then employ Euclidean projection onto X: mig | A t This projection method is applied whenever À & X, ensuring that we always have a
valid point within our optimization domain. practice, we estimate the minimum of f on the domain Th+1 using random sampling or any of the other black-box optimization algorithms, since is cheap evaluate and gradients are also available.
9. Omitted details for Section 4
Proofs are in Section 11.
First, we start with relating the default partitioning scheme ' with A partitioning scheme. To establish the relationship between the near-optimality dimensions of the two schemes, we first need compare the parameters (v, p) of SequooL across both partitioning schemes. This requires a characterization of the cells Arand P The following proposition provides this characterization.
Proposition 9.1. Let K > 0 and oj E Th be the representative of the Ai, cell containing a global maxima of the function. Using fraction of two vectors to denote component-wi wise division,
12

---

Adaptive Partitioning Schemes for Optimistic Optimization
Algorithm 3 Implementing lookahead direction selection strategy Tf(
Require: Current partition tree T, height estimated function f
Xh arg max; fxxh, i), representative of cell Th with the largest function value at height h
Th cell at height h in T whose representative is &h", azis_to_split 0, minimum <-
for i <- m do
Th + + child cell of Th after trisecting axis and having the same representative x*
temp <- Compute minimum f on the domain Th+11
if temp minimum then
ozis to splitpit
minimum temp end if end for
return aris_to_sppp
Añ = a
a aj
Sa with
s [3
m
(8)
Similarly, xf, Idd the representative of the PV cell containing the same global maxima,
Pk = (x:
S K with c c= -3 Atdli
(9)
Proposition 2.5 shows that we can use partitioning scheme perform optimization. We now relate the and p parameters (see Assumption 2.6) of the partitioning schemes P and A.
To establish relationships between the parameters of the partitioning schemes A and the default scheme P, we need to connect the sets Pú and Ai. The following lemma provides this connection:
Lemma 9.2. Let the domain for P be kHd {xx x E [H with 2 3loog vmall Suppose x" E Pj is such that x" = A T Ax". Then, Vi E [1 1]. Ak No have that Akm++ Phdtt
Having established the relationship between the star cells of the partitioning schemes A and P, we can now proceed to relate their respective parameters. The following two lemmas establish these relationships.
This lemma connects the parameters (v,p) of the partitioning scheme P with &. 2 3[luga vmaal to the parameters (VA, PA) of the scheme A.
Lemma 9.3. Let the parameters for the partitioning schemes P,A be (v. p), (MA, PA) respectively. If Lemma 9.2 is (B----mm1111---- (p PA p where 3 = = 2m-I
applicable and P sutisfies Assumption 2.6. Then we have that V
d-m
This lemma establishes the relationship between the parameters (UA) of scheme A and (u,p) of the default partitioning scheme P.
Lemma 9.4. The parameters (VA, (v. p) associated with partitioning schemes A and with 1. Let l1
f" inf # fxx). Then
PA p² VA = -- (19))m-11)--
where h d [loga 1,8 =
d-m 2m-1 and = 3 logs Vmal]
The previous lemmas established relationships between the parameters of the partitioning schemes A and P. They demonstrate that A is a valid partitioning scheme with reduced sequOOL parameter PA compared to the default partitioning scheme p.
9.1. Using À defined over the estimated A
We obtain À using a subspace learning algorithm with evaluations of f at selected points in X. We then use À to define a partitioning scheme Å (as per Definition 2.3) and apply SequooL The impact of using an estimated matrix Å instead
13

---

Adaptive Partitioning Schemes for Optimistic Optimization
of the true matrix A in optimization problem can be quantified using subspace distance. The following is the definition of the subspace distance.
Definition 9.5. ((Chen et al., 2021, Lemma 2.5)) Let A, E Rn consists of orthonormal rows such that AA
Lm
and AA Im- Define two more matrices A1, A1 E R(d-m)xd such that [A A and A A
form two
orthonormal bases for RR. Then the subspace distance between the two row subspaces (A, A) is given by
dist (A, A)
A - A'A - - -||ALÁ' = sin (AA, 2
(10)
where I|-1|2 denotes the spectral norm, and sin θ is diagonal matrix of (o,)) :i= 2, ................................ . where o; are the singular values of ÀAT in decreasing order.
Moreover, we have the following equality:
mmin (AAT) = coss 6m V1 sin2 pm V sin ((A, A) 1) V1 dist? A)
(11)
We observe that assuming (ist(A,A) A) < implies that minn (AAT) & O and rank (A = m.
Given that we only have an estimate Å of the true matrix A, and we perform optimization on the subspace spanned by A, Lemma 4.5 guarantees that we can use A and recover f*. Now, we relate the SequOOL parameters between the partitioning schemes A and Á partitioning schemes.
Lemma 9.6. Let A and Å be the partitioning schemes defined Definition 2.3. Suppose A satisfies Assumption 2.6 with parameters V,A, PA. Let ly g" infzenzaliy g(AA z). Then A satisfies Assumption 2.6 with parameters
V max x u 1 PA PA
where h2 = m + m loga 2ymin and Ri dist (A,A) x2-1
The above lemma demonstrates that the partitioning scheme valid and satisfies Assumption 2.6 and it establishes the relationship between the SequOOL parameters of the Á and A partitioning schemes.
This corollary synthesizes the relationships established in the preceding lemmas, providing a direct comparison between the estimated scheme Á and the default partitioning scheme P. It combines the two-step process of relating A to P and then Á to A, yielding comprehensive set of relationships for the SequOOL parameters, near-optimality dimensions, and associated constants.
Corollary 9.7. Referring to Lemma 4.4, for the partitioning scheme P with K. = 1, we have PA = p
max(v, (1 (1-))mm (100)mmm))1-----000 1)-hn AVAAA CA) < nelveCl and CA ddd (12 up ha, By utilizing Lemma 9.6 and Lemma 4.7, establish the following relationships among the parameters associated with À and P.
. PA PA= Pa max moxxxmaxxu,,yp (0 - , Lg
Pu( CN (p((,,pCC)
B .C = ad 312"-m(12/m)) CP vo his am prohs
with h2 = m + m
logg 2/mma
and h = d [log> 3 llggs vmail with K2 = V1 Vi-diat2 (A.A)
cmm
h3 -- log, (maxtu, (1 9ym 9)m (m)0)-))- log,(v)) h4 - |l0g -
log (va)
(Mousavi-Hossee Hosseini al., 2023). controls the closeness between true and estimated subspace expressed terms of Wille However, for out Algorithm 2, we require an upper bound on the distance between the true subspace and its estimate Á. This lemma bridges this gap by providing an upper bound on dist (A, A) in terms of || [allp and the singular values of W.
14

---

Adaptive Partitioning Schemes for Optimistic Optimization
Lemma 9.8. Given A E Rmmx satisfying AAT m let W E R be any malrix such that rank (W) 2 m and d 2 m. Consider the singular value decomposition of W USV and collect the top right singular vectors in the matrix Vm where v; is the ith column of V. Recollect the definition of sin ( A) and dist (A, A)
À = [[1 V2 from Definition 9.5 and the notation of W. Winfin from section Using 11-1 to denote Frobenius norm and om to denote the th singular value of W, we have that
W W
dist (A, = sin O(A, ((AAA))/
10
(12)
Om
9.2. Supporting lemmas
The following lemmas and assumptions needed to obtain guarantees learning good estimate Å.
Assumption 9.9. (Mousavi-Hooee Hosseiii et al., 2023) The student model a two-layer neural network Equation (7) trained over the data set ((x(0) ())) J221 where the target values y are generated according to the teacher model Equation (1) and the inputs satisfy (0) sid N(O,,a), The link function g()) is weakly differentiable.
Assumption 9.10. "Mousavi-Hossele et al., 2023) For all 1 S S m, S with Vdwl kid bj ~ [O, 1), ma, sid Unif([-1,1), and 6. itd Uni,((-1,1))
j s d, we initialize the NN weights and biases
Lemma 9.11 (Mousavi- Hosssiii al., 2023), Theorem 3). Consider running T SGD iterations over samples satisfying Assumption 9.9, with initialization satisfying Assumplion 9.10, and using the following decaying step size schedule.
Assuming ReLU non-linearity, let ( == 2/eT/ Choose the decreasing step size ne m 7(444" +1) for any > 0. Then, for À with probability at least 1 5.
2(14t")+1 x 2 7 + and x
W
(d + log(1/5)
S
Vm
2T
whenever m Z log(1/6) and T
x²
2+1og(1/0)
The following Lemma is control the subspace distance using compressed sensing algorithm.
Theorem 9.12 ((Fornasier et al., 2012), Theorem 4.1). Let f((x = g( Ax) be function where A is k x d matrix with orthonormal rows, and g is a twice continuously differentiable function. Assume that H' = A HH A is well-conditioned with 0g (H() 2 > 0. Let Å be the matrix obtained from the Dantzig Selector approximation X of the matrix X of gradients of ʃ al m random points. Then, with high probability, the distance between the subspaces spanned by the rows of A and is bounded by:
AAA-AA - AAI S V ax(1 -8)
2V2
5)
1/2
where
1/2-1/9
ck2
1/2 =2=//a// Ck2/2
m.
log(d/ma))
vmg
and C is a constant depending on the parameters Ci and C2 from the conditions on A and g, is the number of derivative directions, e is the step size used in the finite difference approximation, d is the ambient dimension, and E (0,1) is parameter.
10. Illustraiive experiments to motivate lookahead direction selection
Using a partitioning scheme with lower octi-optymality dimension lead to a faster decrease in regret. Empirically, we observe that the regret for SequOOI. applied for budget of 200 evaluations of the function in the Example 2.11 was 5 x 10-10 for the default partitioning scheme and 5.8 x 10-12 for the direction selection strategy in Example (2.11). This example indicates that it can be beneficial to use a direction splitting strategy that adapts to the function being optimized.
15

---

Adaptive Partitioning Schemes for Optimistic Optimization
Additionally, we evaluate the regret for different choices of A. by parameterizing A cos sin cos sin and changing the rotation angle from to 7/s while keeping the direction selection strategy the same as in Example (2.11). Figure 5 shows that the regret varies significantly over the range of angles. This shows that minimizing the angle of discrepancy between A and the true directions of variation (which are the standard æ and 22 axes in this example) is beneficial reducing the regret.
3.0
Lookahead direction selection
Optimal Value of a/b
2.5
2.0
Given particular A and function f. consider the question of identifying an appropriate direction selection strategy that minimizes A A (3 at all heights. The two example strate- gies for f x2) = 1 |z,| 23 we have seen so far are the default round-robin (equivalently 1:1) splitting and the 2:1 splitting Example(2.11) For an A with #/48, we mini- mize the number of near-optimal cells (3rrAAp")) at different heights by choosing the best splitting ratio each height and plot the ratios as the blue line in Figure 4. We see that as the height increases to infinity the optimal split ratio converges to 1. However, at lower heights, the optimal split ratio is greater than and takes its maximum value 1.83 at h =
1.5
1.0
10
20
30 Heights
40
Figure 4. Optimal splitting ratio between the first and second directions. Green curve obtained using the strategy in Defi- nition 10.1
Definition 10.1. Lookahead strategy for direction selection. Given an estimated ff and the current tree of partitions till depth h, the lookahead strategy first evaluates the different number of near-optimal cells for depth + 1 by splitting along each of the m directions. It then greedily selects the direction to be split at h + 1 as the direction that results in the lowest number of near-optimal cells.
In numerical experiment, we see that the lookahead strategy closely matches the optimal split ratio (shown green points in Fig 4) over all heights. This also results in it having low regret than the default partitioning scheme. Empirically, we observe that the regret for Se- quOOL applied for budget of 500 evaluations of the function in the previous lemma was 5.68 x 10-10 for the partitioning scheme A using the lookahead strategy for direction selection, 1.98 x 10-5 for A with 1:1 splitting, and 1.8 10 for A with the 2:1 splitting strategy from Example (2.
10-3
Regret
10-5
10-7
10-9
11. Proofs
10 Angle
15
20
Some of the facts which we use in our proofs.
Key inequalities for the matrix norms include: ||x||>, < ||x||2 < ||x|| Holder's inequality, applicable for p. 2 where 1 + 1 states that xx y| < ||x|| ||y ll. The triangle inequality, valid for any 2 1,
p
Figure 5. Regret at r. = 300 for SequOOL on A with varying 0.
asserts that ||x yllp" S ||>|| - ||xll,
Matrix Norms: For matrix A E R the operator norm is:
|
| sup xş40
| |1
When p 0o, ||A|| maxigism Ej Joyyl and when p 2, ||Al|, omax((), Where Fmax represents the
largest singular value of matrix A. Additionally, the Frobenius norm is given by ||A||
Σn )== la:512
For matrix A E Rmxx of rank r, the following inequalities hold:
1
||]| < |A]| s VF Vn JA
< 1|A I A
(13)
16

---

Adaptive Partitioning Schemes for Optimistic Optimization
For the operator norm
11-1|2- one has
|| S
||
B
|AB||2 2 || Tmin (B), [AB]] | 2 BBl miin (A)
(14)
Suppose a matrix A consists of orthonormal rows or columns, then |A|la = A =
11.1. Proof of Example 2.8
Proof. Consider the function f 222 = ((A)) =1 1-121 with A = [1,0] and -0=)= 1- Let P. be the partitioning schemes defined in Definition 2.2 with x = 1 and parameters (v, p), (M P.A) respectively. For the P partitioning scheme, along the X axis, the side lengths of the children depth h are given by 0-/1/2] and along the Y axis, it is 3 [A/2], Consider f(zj. x2) x2) = [rl and the cell with the representative origin is the P/ cell, therefore
|m|| = 1h/21 3-
h/2 (1/v3)**
According to Assumption 2.6, the appropriate values are V = p, = 1/v3. -//p=1///.. Now consider a rectangle region R with corners {(-3rp", -1), (3up", -1), (3vp", (,, 1), (-3xp", 1)}. Since f f x2) = |z1], V(z1, E R, f f(r1, x2) & 3xp". Thus any cell in P that has a non-empty intersection with a near-optimal cell. Each cell at depth h has an area of 3- 1-11/21 3- therefore
Area( Rt) 4(3(1/V3)
(3rp))
Area(Pn.a) 3- 3-14/213-14
yielding that since (3rp") = 12ppp'p))) from the Definition 2.7 we get 77p 1.
For the A partitioning scheme, we first note that 1. Along X axis, the side length of the children at depth f is 3 therefore
x2) f x2) = |دد| = 3 < (1/3)*,
yielding the values are V = 1, PA = 1/3. Now consider a line segment L with endpoints {(- ((-3vAPP) 0), A 0)}.
Since - f x22 = æi1. V(I1, 0) E f - f(11. x2) S 3// Thus any cell in A that has an intersection with the a near-optimal cell. Every An, cell at depth h has length of 3-h, therefore,
len(L)
2 2(3(1/3))) 88 3-h
NA(3WAPA) 2 len(A(h, i))
where the additional term 2 accounts for cells in A that partially intersect L at its endpoints. Hence Na(3VAP²)) is constant and VAA 0.
11.2. Proof of Example 2.9
Proof: Consider the function (kk) = 1 - |7| with A = 1]. Then, f21, = 9(A) = 1 |m] + 22 For the P partitioning scheme with x = 1. along the X axis, the side lengths of the children at depth h along the X,Y Y axes are 3 [//21, .3 100.3-112 [A/2] respectively. Consider f(af, zz)= - x21 = x21 + ø2/. and the cell with the representative origin is
the PA cell, therefore
[ + xz1 = [h/2] + - [1/2] 2. (h (h-1)/2 < 2V3(1/33)*
According to Assumption 2.6, v = 2/3, p = 1/v3. Consider a rhombus region formed by coordinates ((-3up",00 0), (0, -3pp"), (3mp*, 0), (0, 3rp²)))) Since f f-- (x1, |ar + x2l. V(r,, E a2 I 3pp This says, any cell in that has an intersection with the T' near-optimal cell. Each cell at depth has area of 3-14/213-14, therefore,
< (1 1
3vp"
) (1+
3pp"
No(3up")
s 0(1)
3- [h/2]
3 14/2//
Hence (3(3)) is independent of lt and ypp 0.
For the A partitioning scheme, along the X axis and Y axis, the side lengths of the children at depth h is given by 3 and 3-h .iving that
s - ( = | + x22 = 2 3- < 2(1/3)²* According to Assumption 2.6 the values are 1/A1 = 2, P. = 1/3.
Further, we see from Definition 2.4 that a 22 in this example.
17

---

Adaptive Partitioning Schemes for Optimistic Optimization
11.3. Proof of Example 2.11
Proof. For the P partitioning scheme, the side lengths of the children depth are as follows: along the X axis, 3 3-[1/21 Along the Y axis, it is 3 [A/21, Consider =5) 22) = |zi| + 22. and the cell with the representative origin is the Pj cell, therefore
E1 + 2 = 3- 14/21 +- + 30 14/2
-3-1 2
2 LM/21 12-3-(h-1)/2 $ 223311/v3)
According to Assumption 2.6, the appropriate values are -= -==/-/ p p= and up 2/3(11/33)
Consider a region R which is given by |ei|+a5 & 3xp". Since f" = | + (2), E R. f S 3mp". Thus any cell in P that has non-empty intersection with Rt is a near-optimal cell. Each cell at depth h has an area of 3- 3-1h/213-100 [4/2], therefore
Area(R)
(3 2 Area(Pn,t)
Now, we compute the area of the region formed by the curve [21] + z3 = 3up" which is given by
v 3ugh
| pour -n
dridx2 8/5(3r2"))
Thus,
Ny(3p')) 2 Area(1) 8/3(6v3( 1 1//31 Area(Pn.)) 3 1h/2/ 3 16/2]
=s (1))-
Hence 1/p 2 0.5
The Pj cell contains the point (0, Since P is an axis-aligned partitioning scheme, we can bound the number of cells directly above, i.e., having the same coordinate of their representative that of, Pj by the value 1/3rp//3-100 14/21, In similar manner, we can bound the maximum number of cells having their representative's y coordinate to be the same as that of Pi by 3rp² /3 [h/2], Since P is an axis aligned partitioning scheme, the previous two bounds imply that number of near optimal cells are upper bounded by the product of number of cells along x axis times number of cells along y axis. Thus,
V3 2V3(1/V3)
) (1+
3 2/3(11/33)
1) =0 (0(12))
(3(3up²) < 1
3-11/11
3 3-14/2
Thus, 7pp & 0.5, hence 77p 0.5
For the A partitioning scheme, the side lengths of the children at depth are as follows: along the axis, 3-(h+1) if odd: otherwise, 3-h Along the Y axis, it 3- 1-1//21, Let h is even. consider f (2) |æ + xg and the cell with the representative origin the Aj, cell, therefore
1//h-1)/2 | + 22z = 3- +3 2(h/2) <3 + 3 -3-2(h-1))- < 4-3
According to Assumption 2.6, we have P4 4, PA 1/3, and AP 1-
The A% cell contains the point (). Since A is axis-aligned partitioning scheme, directly above, i.c. having the same x coordinate of their representative as that of, A₁; by the value /3zp" ///////h222 h/22 In a similar manner, we can bound the maximum number of cells having their representative's 's y coordinate be the same as that
bound the number of cells
18

---

Adaptive Partitioning Schemes for Optimistic Optimization
of Pf ; by 3uph/3 /3-h, Since P is an axis aligned partitioning scheme, the previous two bounds imply that number of near optimal cells upper bounded by the product of number of cells along x: axis times number of cells along y axis. Thus,
V3-4-3-4
(1+
(34433"1 1)
3 3.4-33
NA(3vAR')E 1+
65
3-h/2
3-h
When h odd, following the same steps will give (a(PAP')) & 148.
Hence, (VAP)) is a constant and 17,4
11.4. Proof of Proposition 2.5
Proof. We claim that zz Ax", where x* E X is the optimizer of f. This choice of z" satisfies f(A f(ATz)) required in the Lemma. we will now show that the infinity norm of this z" is less than or equal to a.
2²0 = f(x*) as
First, observe that for any [-,,1]4, we can express
convex combination of corner points:
2
2
Cjajs
aj 2 0,
2 0, =1
(15)
Now, let's consider the infinity norm of Ax*
|| Ax Ixx
Σ Ac,aj
(Using Equation 15)
|Acr
(Triangle Inequality of Norms)
2
|ayl |Ac 1|a
(Absolute Homogeneity property of Norms)
j=1
2d
<
>
layl aa
(From the definition of a in the Proposition statement)
1=1
Therefore, we have shown that |20 = ||Ax*1 loc S a, which completes the proof.
11.5. Proof of Proposition 9.1
Proof. Let xj, be the representative point (midpoint) of the Pj cell and x is within the P cell.
Let x a point a hyperrectangle centered at X with side lengths 2xc, where e is a vector of side lengths, Then, this point x satisfies
|z; o кe; for all dl.. Equivalently, this of inequalities can be written as
max.e(1....d)) -r < K. Using the infinity norm, we can concisely express this conditions as x-x; < K, where the division performed element-wise.
For the partition scheme, we perform trisection along each axis in round-robin manner. After iterations, the side lengths given by:
C; = = ا iE (1,....,
(16)
where
d
represents the number of trisections applied to dimension i. Therefore, the cell Pi can be described as:
PV = x E Rd:
x - x
< K
with c |3
h+d-1
(17)
1=
19

---

Adaptive Partitioning Schemes for Optimistic Optimization
From the Definition 2.3, have A - {A a ]h and
Th aER":
a oj
S a with s [3
A m
m
(18)
Hence,
Ai
{ A a
a a--a oi
S a with
= [3
1 m
dd
(19)
11.6. Proof of Lemma 9.2
Proof. Following the Definition 2.2, consider the partitioning schemes and A.
According to Proposition 9.1, express the cell Aj,
A = (ATA: a Q
a a
Za with s= 13
h+m-- m
1==1
At depth h = km + for i E [1 m and k E No. the side lengths simplifies to: [3
13-1(ist)-kpp "
Similarly,
P2 = xx Rd
x-xi
5 with c= [3 A
i=1
At depth h kd + i, for i [1 : d 1] and k No. the side lengths for Pj become:
[3 33-10S0-*14 1
And let consider another partitioning scheme G xP. Let us denote X be the representative of the 9j cell. Using Proposition 9.1, the cell 9% can be written as
Pia+i= = (x:
x
Xkdti
S k}
with
c = [ 10S)) kid j=1
Consider element
A T E Abm now proceed with the following chain of inequalities:
x - Xictsslo S x - x" x21100 + |x
xkdtilloo
(Vector Norm property)
A AJa a A a
+ ||x - K
(x* = A ax))
A AT(a- a*))
||xx Kidtello
A T
|| a0 ||xx xkd+elloo
(Matrix Norm definition)
< m3
a + 3
(From the Matrix Inequality 13) FFrm the Lemma statement, 2 3 [lgg v /mal)
$ 2. 2- *
33 (k-1k
This sequence of inequalities demonstrates that 9(k-1)8- Moreover, know that Gik-1yd C P Therefore, partitioning scheme P with 3lloga Vmma will satisfy:
Abm+s C Plddss
E [1: m - 1k vk e No
20

---

Adaptive Partitioning Schemes for Optimistic Optimization
11.7. Proof of Lemma 9.3
Proof. Since Lemma 9.2 is assumed be applicable, consider partitioning scheme P with 33logg vmaal and suppose
ft SuPxERIy f(x). Let P satisfies Assumption 2.6, then, there exist constants v and 0 < p << 1 such that
sup (fi f(x)) - up". vh E No xEPR
(20)
Since x 2 3[oogs Vmal, we can incorporate Lemma 9.2, which gives,
Abm++ S Pkots
Vi [1: m 11. Ak No
Therefore, we get
sup A
f(x)) - sup f(x) Vi [1: m 1k Vh E No
(21)
xEPheii
Combining Equations (20) and (21), and using the fact f S fi, we have
sup (--))x)) s
sup (f f(x)) s xEPh
S su(pkmit ti
jkm
(22)
A
Therefore, we have
sup Ai
(f' f(x)) s ((pamti) ykmti Ei [1 : m - 1]. vh No
Edti
(23)
Consider PA = pd where
kd +
3 = min
i E m - 1], EN
(24)
km +
Then the sequence of inequalities SuPxE - (fx))(xx) S u(p ) Vi [1: m 1], vk E N ensures that (23) is satisfied for all heights 2 m. We show that B
d+-
2m - the solution to (24). We consider the sequence for k: =
d+i
t m +i
ViE I
First, we show that this sequence decreasing. For any in the range [2, m 2), consider the difference between consecutive terms:
- 1i+ d d+i + (i 1) m + (m (m + + 1)
m d
4+ f,
Since m d, we have m d > O, but the denominator (m i)(m + i + 1) positive. Thus, t,41 t, which says that sequence 4; is decreasing and the minimum value of occurs at i
1: d + (m - 1) d m
mm m + (m - 1)
2m 1
We now consider the general form for any i E N:
kd + i km +
8 min
ie [1: 11
With the observation that
(k: + 1)d + m
kd m 1
(k + 1)m + m 1 km + m
we get B = (d + m - 1)/(2m 1). With this choice of ,3 we have
sup
- f(x)) S v(p km jam+é S (1(p)) ) km+i Vi [1: [1:m 11, N
(25)
xEAiimt
21

---

Adaptive Partitioning Schemes for Optimistic Optimization
Now, we choose MA satisfy (23) for the first m heights. From Equation 22,
sup (f* - f(x)) - vpp = "p'= Vi Vi [1: m 1 xEA;
(26)
S up - W [1 : m m-
(27)
Therefore, VA = up(1-9)mm and PA = will satisfy the Assumption 2.6 for the A partitioning scheme.
11.8. Proof Lemma 9.4
Proof. Consider partitioning schemes P (n: 1) and (n Ri =3ooo vmal) with star cells:
x
x x S n}
Pk = (x:
I 1 9% = [x:XER"
where [3- -
1==1
At height hi d [logs /ma], there are [logs vma] divisions along each of the d-axis. Since at each division the cell is divided into three parts, after [logs /ma] divisions, side length along any axis becomes K loggs vmal = 1. Since we are focusing on the which lies in the domain PS. we have 9 Po- Subsequently, we deduce that 9 S Pi-
implying:
sup XE9
((x) sup (f" - f(x)) vh No xEPE
(28)
By lemma assumption P satisfies Assumption 2.6, with parameters (V, P). Therefore we have
sup (f f(x)) up" e No xEP;
Therefore,
- -f-f((x) S up = up -p- ho-hiph phth Vh E No
sup
(29)
xEG: ka
For depths h E [1 h 1]:
sup (f* - f(x)) p inf f(x)
xE9;
xEn EY
$ (f*
inf xEM
f(x))p-
Using inequality 29 and the above inequality, we conclude that satisfies Assumption 2.6 with parameters (p, maxtu, inf xE (x))).
By Lemma 9.3 and ι 2 3(lors ymal, we conclude:
PA = p², pV
VA = max(u, inf XEX
f(x))p(1-90mm) (mmm-))))mmmm-
11.9. Proof of Lemma 4.2
Proof. Let r)) be the open ball corresponding the closed ball B(x, r). We will first demonstrate that B (c;; (c) BC k²) 1 Vi o j. Suppose there exists point (c, K²) n 1 (c,, K²), then:
||c - c; /olec S ||c, ylloo + ||e -ll < 2
22

---

Adaptive Partitioning Schemes for Optimistic Optimization
However, for lattice points, we have ||c; cyllac 2x', contradicting the above inequality. Next, we show that
((c,,k)) S (N 2x')IITT Ve, C.
(30)
For any y E B(cs, R²) we have that:
|
2 y cillas + ||c:llxc
S K + ||cillo 20 (since E B(x;
= + ||c, 2 z xc
(for some z E k(),k) n B(c,, + 0)
I n' + l|c; 2m + ||z||
S n¹ + k' +
+ 2x'.
Therefore, y (K + 2x') which proves (30). Let N be the number of balls Bic,, R/). Since (* R²) are disjoint and all these balls are contained in (R + 2x') H we have:
N Bx,(B"(),, < Vol((1e + 2*
N. (2x') < (k + 2n')m,
giving that N S (2 ))* t For the lower bound to N, since, B(O, x)) S E B(c,, R²), have that
Vol(B(O, x)) = (2x) s Vol Vol(
Vol(B(c,, Voll( Noll N(2x')
Hence N 2 (x)
Lemma 11.1. Let = [-1/Va.1/Vd Pro = (Q x: x P}. where Q = [A] Al] is an orthonormal matrix, with A E RRad and A E (ddd Denote, Proja, (S) 10 E Rd-m : A X, X RR) and
a'max
|maax oo cj.
maxi Cii m Ant "., maxis a c..]
where Cj are corners of hypercube P. Then:
Vol(ProjA, (Pmi)
II $=m+1
20 max, and Vol(ProjA. (1-1,
II 20 2
Proof. The projection of Pas onto the subspace orthogonal A is determined by:
Proj (Pra) A y E P
Let denote a a [1 m] and a'max(m [m + 1 dl first components and last d - components of the vector a a Since Prot (Q x x P}, the corners of Pro. are given by:
Cros {
(a m| s1) + A Im 1: d O s2) si E (-1/ (-1/V
The volume of the projection onto the subspace orthogonal to A is:
Vol(Proja, (Prm)) =
II
2 max.j
imm++
23

---

Adaptive Partitioning Schemes for Optimistic Optimization
Let Proc. By definition, y Q² for P. Then:
| - ||Q x||o0.
Using the properties of the norm and orthonormality of Q:
|y
<
Q
xx|| S vallo 1Ix 1
00
Since Q is orthonormal, |Q |lxc 1. Additionally, ||x|oo I 1/vd because x E 1-1//V, dj. Thus:
l S 1,
showing that y [-1,1]4 Hence, Prot [-1, Since Prot S [-1, 1jd, the volume of the projection satisfies:
Vol(Proja, (Pro)) S Vol(Projj_ ((-1, 1]
Thus:
Vol(Proja, (1-1,11") 2
II
20 20
1=m++1
11.10. Proof of Lemma 4.3
Proof. Recollect the definition of the partitioning scheme T from Definition 2.3. T represents the equivalent partitioning scheme of A. For the partitioning scheme T, at specific depth h, each cell can be indexed by i, i.e Th, 1 1 S 3 where, 3 represents the total number of cells at depth h, and i is the index of specific cell within that depth. Similarly, For the partitioning scheme P, at depth h, each cell can be indexed by j. i.e, Ph.j i
Definition of the POpt Relation Consider the following definition of the POpt relation:
POpt = ((Tn,,, : Th E (N),,,, Ph. E Wp(e), Th, n APm. # 0}
The sets (e) and Np(e) denote near-optimal cells in the respective partitioning schemes.
A
Pa
(3(3pp))
Notlepp)
Figure 6. Caption
For any h, consider the cell Th (E).). Let be the lower bound the number of elements in POpt that are of the form (T). Then, have: |POpt| (Wr(e)) I. Similarly, for any h, j. consider the cell Ph. (N Let be the upper bound on the number of elements in POpt that are of the form (-. PP..).. Then, we have: [Wz(e)) - 2 POOtt.
Combining these two inequalities, we get:
(+ s (Wr() "
(31)
This inequality provides a relationship between the near-optimal cells in the two partitioning schemes, taking into account the bounds on the number of elements in the POpt relation.
24

---

Adaptive Partitioning Schemes for Optimistic Optimization
11.10.1. ESTIMATING UPPER BOUND
If Ph. is a near-optimal cell, then there a E Ph. such that f(x) Z 5 E. For Ax we get g(y) (AA fxx). y ih then Th is near optimal cell and y TR O AP.... Thus the pair (Th,s PA.) E POpt. To obtain the upper bound u the number of such pairs, suppose that all x E Ph. satisfy f(x) f E. Then the entire region APn. is near-optimal, and we calculate the maximum number of distinct Th,; that can be present in POpt.
We use Lemma 4.2 to obtain an upper bound to u. To apply the lemma, we first approximate the domain APh.j with a hypercube, which we use as x and we obtain a lower bound on the side-lengths of Th cells which will be used as a n'. These approximations allows us to effectively utilize Lemma 4.2 in our analysis.
Using Proposition 9.1, the cell Th and Ph.j can be written
This far R",
a O'h,i s
S a
with
[3
htm-i
Ph.i fx E Hd,
x Xh.i
S with
|3-1 اياي
c
For all X2 E Phisi consider
||Ax]
Ax2 ex we have:
Ax1 Ax2llo
S | 0o || 11 - X21l00
(from the Matrix operator norm definition)
mml X1= X211,0
(From Matrix Inequality 13 and || 1)
Vml [1= - x2 + Xn,, Xhilloo
$ m x1 - -xnillo + v ||21
xnilbo
S 2/m3-k
(Let h = kdd + i)
Now, we estimate the side lengths for the This cell, by computing s
h + m -j j
kd m 1i-- j S
kd + d
d
S
(k
1)- +
m
m
m
m
Hence 3-L h+
2 3- (1+(+++))
We set 2/m33 n a3 (1+((+++++) ) and invoke Lemma 4.2, derive the upper bound to Thus,
2 2/m3-* &
2 )"=)))
( (2(2 6 m/ m
m
us 2
a3 a3-13-101 (k+1)
(2+ + G/yg/////m m
(12 (mdg/))mnddkkd-m
11.10.2. ESTIMATING LOWER BOUND 1
Recall the definition of A from Definition 9.5, If AN,; is a near-ottimal cell, then there is ax E A,, Consider x' = X + A y.,, where y E Rd-m_ Then, f(x') = g(Ax') = g(Ax) = fxx). Hence the entire domain {x 1x+AAy AlY ly dd x + ALy E [-1, is a near optimal region. Suppose Pr., has a not zero intersection with the above domain, then the cell Pa.j a near-optimal cell. We thus count all these cells to get a lower bound
s.t. ft
25

---

Adaptive Partitioning Schemes for Optimistic Optimization
Vol(Proja_ (Po.o)) nz (oo(Proj (Ph.u))
I 2(
(Numerator through Lemma 11.1)
11 2max 9 x3
1==++1 (1/vd)2 m 9. cj
(Here oj are corners of hypereube [11,
Il l1==+11 2 max mmaxxsjss" q X,
Il: m max c,
-ii=--1 3 max q Cj
(1/ Vd)
2 (1/d)² mgg(ddm))
3 k(d-m)
Hence, the lower bound (1/d)d-m3he) Thus, using Equation 31, we conclude that
[a(()) & (3vp"))) 3 (12mm)"
(32)
11.11. Proof of Lemma 4.4
Proof. To start, we recall the relationship between the parameters of the two partitioning schemes as established in Lemma 9.4. Specifically, we have:
PA = p², VA VV
max(v, f
inf ()m 9)mm-))1m))- 11 XENTE;
For brevity, we denote v/ m, inf x f(x)).
From the definiton of near-optimality dimension for the P partioning scheme, we have:
Nip(3up²) S Cp Dr
(33)
Now, consider A
3v' 1)m-1))-h
Sh (v' a0 310m 1--5mm--- 1) 11-11111h1-0 - (v)
S 3tp Hog (v' oa osen is hi (1)-
< 3vp hi l 1)(m-))-- (v) [v)
r-h h-
(Denote hu loogp (2' (11-8)(m-1)-b) - -log (v) )
Now, consider
) (3pp3
(3RAP1) S 32p" 32sh-hhs hs)
< 3d0 (12V No (3pp" (1
(Using Lemma 4.3)
< 3dd (12Vm) Cp no hk-
(Using Inequality 33)
(0fd-m(12Vm)) Cp
Cp "r ha top-ni pph pph
Therefore, have:
NA(3UA/PX)) (3 (1 hs up
4h > ha
26

---

Adaptive Partitioning Schemes for Optimistic Optimization
For heights h E [0: hg 1]. since the right-hand side quantity is monotonically increasing, we can use the value of the right-hand side at depth h hy in the above expression, which is 3 (0 (12
Therefore, we have
NA(3VA/P1") 3"d "11/mm)""" up hs up h 1n
-3ddd-m11 (12 up his PA
This implies that A S 1/p B3 and the constant CA is given by 3d (12 CCp 1/
11.12. Proof of Lemma 4.5
Proof. Consider x= = (AA ) then
T x²) 9(AA T 2²) - - TAATAAA (AA (AAT)-'AS )'1''xxx)) f(À
= =((Ax") = =((x).
Now, we show that
(AA T Ax*
2
2
(A
Ax"
(Vector Norm Inequality)
< (A )-1 || ||Ax* l12
(Operator Norm Definition)
(AA T 5ー1
Tmin (AA)) )
||Ax* l12
(Since, O (AA > 0)
mmin (AÁ'
(AA AA
||Ax"112
(From Matrix Inequality 14)
min (AA)
|Ax* l2
(From the Equation 11 and ||]]] = 1)
dist? 2 (A, A)
m AxxII 11
(Vector Norm Inequality)
1 dist? (A, A)
/ma
dist? dist?(A, (A,
For some of the proofs, use the following equivalence of partitioning schemes.
11.13. Equivalence of partitioning schemes
Consider the partitioning schemes A and T which are defined in Definition 2.3. For every a Th,b, there exists a unique TTa. ax This establishes an equivalence:
X An, such that x =
Vx An,i: f(x) f(A a) = - = =(())
(34)
where f is optimized on Ar, and g on Th Thus, optimizing f over A is equivalent optimizing 9 over T.
Similarly, for the partitioning schemes A and T, we have; Va Th. Ex An, such that A a. This leads to:
Vx E Ans. f(x) f(A a) A(AA a) = g(a)
(35)
where g defined on Th, and 9 on Tr Therefore, optimizing over A is equivalent to optimizing ğ over f.
27

---

Adaptive Partitioning Schemes for Optimistic Optimization
11.14. Proof of Lemma 9.8
Proof. From the notation section 7, we have W W WA WATA A. Next, consider the singular value decomposition (SVD) of W, given by W USVT, where U E RexP and V Raxd are orthogonal matrices, satisfying UU U U Ip, VV V V = La and S Rxxd is diagonal matrix.
We have this relation || 01 (W: 2 ... 2 o,(W) 2 0, r= min{p rank(W) (W) = r 2 m. Thus, we collect the respective leading m columns of U and V, denoted as U, E IR and V1 E Rdxm, respectively. The remaining columns are denote by U2 1Pxp-" and V2 [Rdxd-m. Since, columns of
(eppp,d). dj. From the Lemma assumption, we have
U1 and U2 forms a orthonormal basis for R we have:
U U = Im and U2 0mxp-m
(36)
Then the SVD of W can be written as: W = U + U2S.V2 and from the lemma hypothesis Å = V, Now, consider the implications of this decomposition for the proof. Consider,
W(I- A AA
2 W([- - ATA) A)
(From Matrix Norm Inequality 13)
[. - (I- A TA)112
(SVD of W)
A A)) 2 U (I- + (I ATA))
|UT|
| 2
(From Matrix Norm Inequality 14)
= V. - AT
(Using Equation 36)
2 mmin (Si) VI - A
ATA) A)
(From Matrix Norm Inequality 14)
Á ATA)/12
0m
AATAL
A T, .AT] is orthonormal matrix, thus A A A A Ia)
dm
ÁATA
A
<|AT
0m
= 2
2
AATALAII
(From Matrix Norm Inequality 14)
0m
ÅA
(A consists of orthonormal rows)
Fm
sin O A)
(From Definition 9.5)
2
Since Fm 0, we have
W(I A
W(I - W(IATAI)
ssi 0(A, (A) A)
m
m
11.15. Proof of Lemma 9.6
Proof. Using the partitioning scheme equivalence from Section 11.13, we can work with partitioning schemes T and Ý in place the and A partitioning schemes.
28

---

Adaptive Partitioning Schemes for Optimistic Optimization
Let 2/; 2/ be the representatives of Th and th cells respectively. Then
Th = 2 E Rm
Zh. 2
S a
with
8 3
h+m
1=1
8
and
E R
2/2
mma
with 8= [3-
h+m-1
1=1
dist? (A, A) dist?(A,
For brevity, denote K2
v distt (A, Let z" denote a maximizer of the function g, i.e, z" E arg max xeari g(z).
Given that g(z) = (AA z) and that AÅ an invertible matrix, we can identify a corresponding maximizer z for 9 such that: 2g AÂ i. Under this transformation, ((2)) will be maximizer of the function g.
From lemma assumption, T satisfies Assumption 2.6, therefore we have:
4h No, sup (g- g(z)) MAPA TET,
(37)
We aim to control
vh E No. sup (g" ğ(z)) sup (9 sAA z))
(38)
zETr
x
We choose some height and represent it h km + i. Let denote:
Rn = (AA 2: 2: F.
Now, we show that:
Rkm S STkm-mk'
where &' = logs Kg -1
2ymma
Consider point AA T
z from the set Rem. where z E Trmm By definition, z satisfies the following condition:
Iz 2pm I 3 3
(39)
Now, we show that AÀ z E Tim-mbrr
We begin with the following inequality:
)m AÅ? z
20
Lik- km
2 +
AA T
AA
T z
(Using zy AA zi)
21
+
AA
(z)
%
(Triangle Inequality of Norms)
80
< (1 x) +
AÁ
(z)
2)
(z² Th cell. Thus [ z 21 S 3 k
< 3 1k- (k- a +
AA
|| z
OOperator Norm Definition)
53 (1- vm ||z,
2||00
(From Matrix Inequality 13, 14 and | =||
5 3 a + vm ||
- 7mmm + 2/ 20 + Vm 1k 2|1oo
< 3 16- x) a + mm $2
(using Inequality 39 and z E &+*,m) km)
53 3- (b-x a + 3 (( - 1)
(Suppose k' chosen such that 2 S (N2 - 1)3²()
ax23 -xx23((k- (k-K)
29

---

Adaptive Partitioning Schemes for Optimistic Optimization
From the above inequality, conclude:
Rkm S T km-m Jogs
2ummu a2-1
Using the above set containment, for any height = km + i, we have
Ri Rkm CT km-m logg
2y/mx2 #2-1
km-m
logs
2v/ma2
+
First and the last containment are valid from the round robin paritioning scheme. Substituting, h km we get:
RR S CT
h-m logs
2y/mer
12
m
2/mma Define: h2 logg> k2-1
Using the Inequalities 37, 38 and the above containment, conclude:
sup (g" - -(()) s VAPA th ha
vh h2
(40)
zeT;
For height E [0: h2 - 1]. we know that:
inf [(z) 2 inf g(z) xET
xET
which implies:
sup (g" ((z)) = inf g(z) S (g" z
inf T
{(z))P ho
P'
x
Combining 40 and the above inequality, we conclude that 7 satisfies Assumption 2.6 with parameters:
(PA, max
inf =EN2OE]
g(AAz))p Rw)
11.16. Proof of Proposition 8.1
[W1, W2, Wa..... wpl E Rdxp, where we assume without loss of generality that the vectors (W1, W2, ... W are linearly independent. If the vectors were dependent, we could consider only the independent vectors without changing the Span W1. W wp). The orthogonal projection matrix P onto Span W1, Wa...., Wp given by A(A A) TAT
Proof. Let
(Pw,) w.. x, where the equalities hold due the following: First, PT P because P a projection matrix and thus symmetric. Second, Pw; w; since w, is in the column span of A, and P projects onto this span. Therefore,
For all x E Rd. consider (w.P)x= (P w;) Tx (
express f(x) as
p woo(w Px + b.).
f(x) Σ
0 w x b,)
Σ
(41)
1=1
Since (x x') 1 (wi, W....., Wp),
Wp).Px Px=
Px' and therefore using Equation (41), f(x) f(x').
11.17. Proof of Lemma 4.6
Proof. Using the partitioning scheme equivalence from Section 11.13, we can work with partitioning schemes T and ř in place the and A partitioning schemes.
30

---

Adaptive Partitioning Schemes for Optimistic Optimization
An arbitrary cell Th in T is defined as:
Zn,i with
Th
2: Z:ZE R"
aa
me
(42)
S
and an arbitrary cell Th.s in I is defined as:
Th
2:22 R
2 Zn
I aym
with $ 13"
A+m-
m0
m
(43)
1 dist dist"(A,
We optimize the function ī(z) s(AA x) over T. while optimizing g(z) over T. For near-optimal cell Th No (3VT the following holds:
sup g(z)=
sup ) Th.
A(AA 2) - -3
(44)
Th.
where the inequality holds because Th is a near-optimal cell by assumption.
We aim to count the number of cells in T that satisfy the following near-optimality cell condition:
sup
g(AA 2)29" -314-17
(45)
zeth.
Since, u7p9 > VTp the above condition is satisfied by
sup g(AA 2) -3
(46)
z T
Using relations (44) and (46), we observe that since the function 9(AA 2) is identical in both cases, it suffices to work with the domain of the cells. Define:
((AAA ((AAA)-IZ:ZE lz:z Th.i.
To obtain an upper bound to the number of near-optimal cells in the partitioning scheme Ý. we consider every cell in / (Tr.)) that intersects with B as potentially near-optimal. For simplicity, we enlarge the domain B into hypercube m.
The set B is the transformation of the cell Tr.; under (AA - Since the transformation linear and invertible, remains a bounded region. However, to simplify analysis, we enclose in a hypercube. By ensuring that the hypercube fully contains B, any cell Th.s that intersects this hypercube is considered candidate near-optimal cell.
31

---

Adaptive Partitioning Schemes for Optimistic Optimization
12,, 22 E Th consider,
(AA ) 21 (AA (AA))11 )- )-1
00
(AA
21 22|100
(From the Matrix Operator Norm definition)
mm
(AA )-1 || 82
(From the Matrix Inequality 13)
(AA -1
|z1 B2 ac Fmin (AA) )
m
(Since, minn (AA) > 0)
min (AA
(AA AA
|||] 22
(From the Matrix Inequality 14)
min AA
m Iz]
Z2 12
(| 1)
min (AA
Vm
2a3 k
mmin (AA
203 kk
(From the Equation 11)
d A)
(1) is true from the following inequality,
211 Bi.i
Zh.5 32
21 Zhh + Bh.
22
|2| - 22llo0
diag (s)
|(
111 Bn.i + 2/1,
< Idiag (s)
$ 5 h-2x
Hence:
m
B C 203
H
dist? 2 A, A)
To establish upper bound for the near-optimal cells of 7 partitioning scheme, consider the hypercube 2a3-k
V (A.AA) H as potentially near-optimal. We can then count the maximum number of cells in the 7 par- titioning scheme at height that can intersect with this region.
vm
To invoke the Lemma 4.2, we have 2a3 1/id and need the side-length of the cell This cell or for
simplicity, lower-bound to side-length will be w'. And the side-length of Th,s cell greater than 2 (A++1)
a
V1 (A,A)
Hence, the maximum number of cells of Tr., that can be tiled inside the hypercube with side length 2a3 - are
TT
(i,
2a3
T / di-dis (A,A)
m
1 +
2-3-(k+) (k+1)
a m
V1 /-ddist
Hence, upper-bound to the near-optimal calls of 7 partitioning scheme
Vh 2 0, (3 I 4tt (3uT
(47)
32

---

Adaptive Partitioning Schemes for Optimistic Optimization
11.18. Proof of Lemma 4.7
Proof. From the Lemma 4.6, we have
vA 2 0, N4(3u4d44) S 4th (r
(48)
Using the above relation, relate the near-optimality dimension. Suppose, 1T (UT, dimension of T then,
(UT, PT: PT;CTT is the near optimality
vh 2 0, NT(3vTp44 s CTP7"Th
(49)
From Lemma 9.6, we have the following SequOOI, parameter relations:
" max -" inf ((A 2)}/07 . = PT where h2 m++m logs 2 m aE
vm
and
1 dist (A, A)
For brevity, denote 1ly max g" inf iif g(AA T 2)}. Now, consider 3
h-ha 3VT pu (1'y PT h2 - (UT) PJ
33/ PT
log (UTT - log (UT) p4
333Tp PT
-3T PT has
(Denote h4 l0o (T) log (PT)
pij
Next, we examine N₂ N2(3 (324
< N (3UT h-)
< Thh N (3UT PT A--
(Using Inequality 48 and N4 S SN (30440p7)
< TT' CTPT or (b-
(Using Inequality 49 and vh > h4)
Therefore, we have:
Nf(307p7) S 4th CC vh hes
(50)
For heights [0: :0:Aa has 1). we can use the value of the right-hand side at depth h h4, which is 4" Hence, we have:
N+ S Tth 4Th CTP. aT
Po nTh
Yh 2
CT"TT
a7 nrh
P7
wh 2 0
Therefore, we conclude that 174 S 17r and C7 = 4m parh.
11.19. Proof of Proposition 3.1
n² Proof. Let Amax nlogn+ To
as given in the lemma statement. SequOOL opens
hmax A
cells at depth h for all
E [1, Amax]- Additionally, we utilize samples for every e heights to leamn f. The total number of samples used to learn up to height /max is thus
Thmax Each cell opening in SequOOL requires 3 samples. Therefore, the total number of
openings performed by Algorithm is given by Σ Romax
hmax
Thmax
According the proposition, we need to show
1=
3c
33

---

Adaptive Partitioning Schemes for Optimistic Optimization
that this quantity is S Consider, total number of openings:
mmax i
mmax T 3c
n22
T
(Definition of mmax)
nlogn Tn 3c
3c
1=1
n
T
(logn
+
(Recall the definition: logn A Σ i)
nloggn
3c
3e
n
Hence, the number of openings made Algorithm does not exceed n.
11.20. Proof of Theorem 4.8
We start with the Theorem 5 of (Bartlett et al., 2019). We restate the theorem, adapting it to our notation and incorporating the dependency of the parameters on the partitioning scheme P:
Theorem 11.2 ((Bartlett al., 2019), Theorem 5). Let W be the standard Lambert W function. Suppose I along the partitioning scheme P satisfies Assumption 2.6 with associated (VP,PP), Cp > 1, and near-optinality dimension Mp (up, Cp. Pp) parameters. Then, after rounds, the simple regret of SequOOL is bounded as follows: For mp > O. we use Corollary 6 of (Bartlett et al., 2019). Let ñ |/logn]| Tpp log(ll/)))/(CCCC
If 1/p = 0, rn S Supp
m
mf > 0,Tn S Vp
up
ing
To invoke this Theorem for our proof, first we apply the theorem for the partitioning scheme Á. 4.7 shows that A is valid partioning scheme, i.c., it satisfies 2.6, hence we can invoke Theorem 11.2. Thus, for our partitioning scheme Å, denoting ñ |//lgg na log(l//_.ggggo (///11///////// (C))) the regret is bounded by
リ On rn MAPA
If 7 0, SVA
log
A
2
Corollary 9.7 relates SequOOI. parameters and gives,
PA PA= ,², MA max/max (u, 10 (1 -- _410p hz
PAl pp((.ppC)
B CA= 3 dd d (12/m)m Cp ha nm pohhs
Now, we substitute these relations in our regret bound get the upper bound in terms of default partitioning scheme parameters.
(1
Sis p oT 1g30 [1
if hpp 0,
In S
max(max (1 hi 1.30 sio
a log ni
if kpp > O,
Where C1 3dd ( (12 Cp-pphshhhhe whhss 4 pp and ń |n/logn| mp log(1/p)/(C with hos m logs
2 mnZ
and hn d llogs 3llog vmail with x2
mm
-
Vi-dist? (A.A)
hgg (max (v. 1,1p)p 3)mm)mmmm---m (10-)mmm1)-- log,(1)) .hs = |08501
- log (vA)
34

---

Adaptive Partitioning Schemes for Optimistic Optimization
12. Additional Experiment Details & Results
12.1. Test Functions Experiments
We implemented SequQOL, SOO, and RESOO ourselves due to the absence publicly available open-source code for these algorithms. For DiRect and Dual Annealing, we utilized the implementations provided in the SciPy library's ' optimize module. The CMA-ES algorithm was sourced from its dedicated project repository'. REMBO and HesBO implementations were derived from the original HesBO repository". Bayesian Optimization implemented using the repository 3.
12.2. Multi-Inder Functions Results
We present additional experimental results further demonstrate the effectiveness of our approach. Figure 7 showcases the performance of various algorithms on low-dimensional multi-index functions with d = 5 and Our algorithm consistently achieves lower regret across different test functions, including Sphere, Branin, Ellipsoid, and Rastrigin, often reaching zero regret with fewer samples compared to competing methods.
12.3. Training Details of LLM Quantization Experiment
We implemented our Large Language Model (LLM) code on hardware equipped with one Quadro RTX 5000 GPU having 16GB VRAM. For comparison, we ran AWQ baselines using the original authors' code, which also served as a foundation for developing our proposed method.
To optimize the neural network used in Algorithm for our LLM Quantization objective function, we employed the Ray package for hyper-parameter tuning" We used Adam optimizer and our search space included hidden layer sizes (500, 1000, 2000, 3000), learning rates (log-uniform from 1 10-1 10-1), weight decay (log-uniform from 10-2 to 1 x 10-1), and learning rate Step Decay with gamma values (uniform from 0.9 to 0.99), and step sizes (500, 1000, 2000).
We utilized early stopping to prevent overfitting.
The neural network was retrained on SequOOL samples every heights, with the look-ahead strategy applied up to height of 60 and performed round-robin direction selection after this height.
'nttps://github http://hw...aoe/eeaaaaaaaaaaaaaa
hikttss:/github.com htw.a//......aaaaaaaaaaaa//aeeaa
http:h/..w...aapeesaaga.ginaaaaa wttp:pptiiiiiiiiiiiiiiiiiiiiiiit Baaoo////aaaaaaaaeoaaeeeae anOpt imi zation on
35

---

Adaptive Partitioning Schemes for Optimistic Optimization
1+ (x] 1)2 + (x5 - 1)4
Rastrigin Rotated-5d
10-5
10a
Regret
Regret
10
10-
10
10-10
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Sphere Rotated-5d
Different Powers-5d
10
10:
Regret
Regret
10-5
10
10-10
10-9
750
1000
1250
1500
1750
2000
250
500
1000
1250
1500
1750
2000
Rosenbrock-5d
Styblinski-Tang-5et
10a
10
Regret
Regret
10-3
10-3
10-9
10-10
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Hartmann-6-25
Branin Rotated-5d
10-1
Regret
10-1
Regret
10-6
10-3
10-1:
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
Ellipsoid Rotated-5d
Sharp Ridge-5d
10
Regret
Regret
10-1
10-²
10-10
10-9
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
CMA-ES
REMBO
Random Search
500
SequOOL
Dual Annealing
HESBO
SequOOL on Á
RESO0
Bayesian Optimization
Direct
Figure 7. Regret Plots: Legend for the plots are arranged in the order of their performance. Algorithm (SequOOL on .A) uses 100 additional samples learn the subspace through the Fornasier al. (2012) approach. Our Algorithm, SOO, RESOO, SequOOL hudget algorithms, so we run these algorithms using 100 equally spaced budget values between and 2000 and plot the regret at the end of each run. For the randomized algorithms, took 10 trials and plotted the median curve (thick line) and and 95 percentile Random Search run on A.
36


Reviews:
[{"review_id": "BjxEwsebRb", "reviewer": "Reviewer_QRGR", "summary": "The authors propose two different versions of learning partitioning ideas for Optimistic Optimization algorithms for black-box optimization. The first, uses a two step approach that first learns the partitioning and then optimizes. The second updates the partitioning while optimizing. The authors support their claims with theoretical and empirical evidence.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We respond to the reviewer's questions below.\n\n> Claim 1: We demonstrate the benefit of using a learned partitioning scheme & Claim 4: We pose the quantization of Large Language Model (LLM) as a high-dimensional black-box optimization problem\n\nWe thank the reviewers for recognizing our claims. Our approach enables a more faithful application of the AWQ quantization strategy: We quantize the entire LLM end-to-end while the AWQ algorithm had to perform an independent grid search over each successive layer. Since quantization is a \"perform once, reuse many times\" operation, and small improvements in the perplexity score are often critical, we believe our approach could be fruitfully applied on other larger models. We believe this to be one of our main contributions. Regarding the search budget values in the experiments, grid search had long stopped improving and hence we had paused its execution at 9 hours. We will match the compute time budget in the updated version.\n\nVariant 1 of our algorithm exploits a low-dimensional ridge structure in the objective function. Since the LLM quantization problem did not have such a structure, variant 1 did not provide an advantage. However, as the experimental results show, Variant 2 can provide an advantage even when such a structure is not present.\n\n> Claim 3: Empirically, we demonstrate the improvement in optimization error\n\nThe contribution statement is a general claim. Specifically, compared to RESOO, our method achieved zero regret on both the Rastrigin and Styblinski-Tang functions, whereas RESOO had a regret of $5.5 \\times 10^{-3}$ on Rastrigin. For Styblinski-Tang, our method required approximately 900 evaluations to reach zero regret, while RESOO needed 2000. \n\n> Where are Algorithm 2 results for Figure 2?\n\nThank you for pointing this out. The experiments in Figure 2 were on synthetic multi-index functions with a low-dimensional structure. We ran variant 1 to verify and demonstrate the benefit of learning the low-dimensional subspace. However, as per your comment, we could also run Algorithm 2 on these multi-index functions. We will run it and add those results to our revised draft.", "claims_and_evidence": "Claim 1: We demonstrate the benefit of using a learned partitioning scheme for existing derivative-free optimization algorithms such as SequOOL.\n\nOn standard toy optimization problems, the learned partitioning shows improvement over SequOOL. This advantage doesn't show in the real-world problem of LLM quantization. Here, variant 1 performs worse. Variant 2 shows small (not clear whether this is significant as the others don't provide std) improvements, but also has 20% more compute budget. I consider this a mixed data point with clear need for improvement in the latter experiment.\n\n\nClaim 2: When the function is a low-dimensional multi-index function we theoretically prove improved regret bounds shown in Table 1.\n\nI'm no expert, but looks ok to me.\n\nClaim 3: Empirically, we demonstrate the improvement in optimization error for several benchmark functions including Rastrigin (multi-modal), Branin (multiple minima), and Sharp Ridge (non-differentiable).\n\nThis is a strictly stronger claim than Claim 1 and thus those remarks apply here as well. Additionally, we see that RESOO shows similar performance on average compared to the proposed method. Thus, this claim has no strong support.\n\nClaim 4: We pose the quantization of Large Language Model (LLM) as a high-dimensional black-box optimization problem and obtain an improved perplexity value.\n\nThe authors show an improvement, but also use 1/3 more search budget. Thus, this is no fair comparison. Improvements seem rather small as well.", "methods_and_evaluation_criteria": "The authors choose high-dimensional problems which makes sense for their problem. Most benchmarks are \"toy\" functions. I'd like them to tackle real-world problems instead. NAS benchmarks could be one example of high-dimensional benchmarks with stronger connection to practical relevance.\n\nAllowing different compute time for the result in Table 2 makes little sense since we are no longer able to compare the performance of different search methods.", "theoretical_claims": "I tried follow the authors reasoning, but I'm a more applied researcher. I leave the evaluation of this part to my fellow reviewers.", "experimental_designs_or_analyses": "Yes. Covered in \"Methods And Evaluation Criteria\"", "relation_to_broader_scientific_literature": "In my opinion the authors describe it very well. They could have covered some other learning-related work as well. I leave pointers below.", "essential_references_not_discussed": "This might be also interesting work for the authors. Instead of using Bayesian optimization on a random lower dimensional space, there is work learning this space:\n\nWenlong Lyu, Shoubo Hu, Jie Chuai, Zhitang Chen: Efficient Bayesian Optimization with Deep Kernel Learning and Transformer Pre-trained on Multiple Heterogeneous Datasets\n\nMartin Wistuba, Josif Grabocka: Few-Shot Bayesian Optimization with Deep Kernel Surrogates", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "I found it hard to identify which are the algorithms presented by the authors at times. Maybe give them a name instead of referring to Alg 1/2?", "questions_for_authors": "Where are Algorithm 2 results for Figure 2?", "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": "", "extra_scores": {}}, {"review_id": "AdrYgO34Si", "reviewer": "Reviewer_4oos", "summary": "The paper proposes an adaptive partitioning scheme for optimistic optimization that extends existing gradient-free algorithms such as SequOOL. The authors consider both a two-stage and an interleaved algorithm. In the context of multi-index functions (defined on a n-dimensional subspace within m dimensions), they prove an improved simple regret bound for their method compared to SequOOL and another baseline. The algorithms are evaluated empirically on a set of synthetic functions as well as a LLM quantization task.\n\n### Update after rebuttal\nMy overall assessment of the paper remains unchanged.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We respond to the reviewer's questions below.\n\n> I would have also liked to see SAASBO and TuRBO.\n\nThank you for sharing these two relevant baselines. Previously, we tried to ran the TuRBO method and after 100 evaluations the computation time is very large, hence we did not include it in our results. We will try to run SAASBO for 2000 evaluations and add it in our revised draft.\n\n> It is not clear what the settings were that were chosen for the baseline methods (e.g. dimensionality of the embedding dimension for REMBO and HESBO).\n\nThank you for pointing this out. dimensionality of the embedding dimension is choosen to be equal to the value $m$. We will add these details in our revised draft.\n\n> The evaluation of the random embedding Bayesian Optimization (REMBO, HESBO) on the low-dimensional problems in the appendix appears rather odd. \n\nWe thank the reviewer for the suggestion!. We will include standard Bayesian Optimization in the updated version. \n\n\n> Why is Algorithm 2 not evaluated on the test functions?\n\nThe experiments in Figure 2 were on synthetic multi-index functions with a low-dimensional structure. We ran variant 1 to verify and demonstrate the benefit of learning the low-dimensional subspace. However, as per your comment, we could also run Algorithm 2 on these multi-index functions. We will run it and add those results to our revised draft.\n\n> The results in Figure 2 are quite hard to read.\n\nThank you for the suggestion. We will incorporate this in our revised draft.  \n\n> Some of the discussions appear to focus on extremely small differences (e.g. on the order of 10^-10 - 10^-12 in Section 10). \n\nThank you for your feedback. Section 10 presents an illustrative experiment to motivate lookahead direction selection. The function $f(x_1, x_2) = 1 - |x_1| - x_2^2$ is evaluated with different parameterized choices of $A$, without randomness. Thus, variance is not a concern, and the goal is to highlight potential benefits of our proposed strategy. \n\n\n> Algorithm 1 does well on a couple of the examples (however, the authors don't provide much intuition for why htat is the case)\n\nOverall, Algorithm 1 is expected to perform well when a low-dimensional ridge structure is present in the objective function. This is because our approach learns the low-dimensional structure and performs optimization on the reduced search space. The effect of the reduced search space can be seen in our regret bounds and is demonstrated in our experiments. Our Algorithm 1 is a two-stage algorithm where the first stage learns an adaptive partitioning scheme and the second stage uses it for optimization. In Figure 2, we used 650 samples for the first learning stage; consequently the anytime regret till 650 samples is high. While standard approaches like the doubling trick can be used to convert a budgeted algorithm to an anytime algorithm, they are not the most effective, and we will develop an effective anytime algorithm in future work.\n\n\n> For the LLM example, while a nice and practical real-world example, it is not clear how meaningful the improvement is compared to the baselines\n\nThank you for your feedback. Our response is as follows:\n\n1. Our approach to LLM quantization enables a more faithful implementation of AWQ, leading to improved quantized model accuracy.  \n2. AWQ is a widely used quantization method, as evidenced by several publicly available models:  \n    \n   - [Huginn-13B-v4-AWQ](https://huggingface.co/TheBloke/Huginn-13B-v4-AWQ?utm_source=chatgpt.com)  \n   - [Capybara-Tess-Yi-34B-200K-DARE-Ties-AWQ](https://huggingface.co/TheBloke/Capybara-Tess-Yi-34B-200K-DARE-Ties-AWQ?utm_source=chatgpt.com)  \n   - [ChatQA-1.5-8B-AWQ](https://huggingface.co/bartowski/ChatQA-1.5-8B-AWQ?utm_source=chatgpt.com)  \n\n3. Quantization is a one-time process, and prioritizing accuracy at the cost of compute is justified to ensure a high-quality model.\n\n\n> For the experiments, it appears that you generate a single A once per function and then run multiple optimization runs\n\nWe do reinitialize the subspace by generating a new $A$ after each trial to ensure unbiased evaluation. We will clarify this in the revised draft.", "claims_and_evidence": "* The theoretical results are supported by a large set of technical results and proofs (which I have no particular reason to doubt but I also did not double check).\n* The empirical results are less convincing: the performance of the proposed methods is mixed, and it is not particularly deeply explored by the authors as to why.", "methods_and_evaluation_criteria": "* The benchmark setup appears generally reasonable, modulo the comments below. \n* I would have also liked to see SAASBO (https://proceedings.mlr.press/v161/eriksson21a.html) and TuRBO (https://proceedings.neurips.cc/paper/2019/hash/6c990b7aca7bc7058f5e98ea909e924b-Abstract.html) as additional baselines, but I don't think this is critical.", "theoretical_claims": "* No. This is a highly technical paper in an area that I'm not very familiar with so this was not feasible.", "experimental_designs_or_analyses": "* It is not clear what the settings were that were chosen for the baseline methods. Without this (e.g. dimensionality of the embedding dimension for REMBO and HESOB) it's very hard to interpret the results of the experiments.\n* The evaluation of the random embedding Bayesian Optimization (REMBO, HESBO) on the low-dimensional problems in the appendix appears rather odd. It doesn't make a lot of sense to generate some lower-dimensional embedding in a 5-dimensional space if the evaluation budget is 2000. The proper comparison here would be to just use standard Bayesian Optimization.\n* A more clear ablation of the performance as the ambient dimension increases would have been useful to understand the behavior.\n* Why is Algorithm 2 not evaluated on the test functions?\n* The results in Figure 2 are quite hard to read. I recommend focusing on showing traces from a smaller number of functions and relegate the rest into the appendix. You can also aggregate the results across functions in a more compact format to keep the key message in the paper.\n* Some of the discussions appear to focus on extremely small differences (e.g. on the order of 10^-10 - 10^-12 in Section 10). How relevant are these differences? Can we actually conclude anything from them them given the variance in the results?", "relation_to_broader_scientific_literature": "The primary contribution of the paper is to propose an adaptive partitioning scheme and proving improved regret bounds for this compared to non-adaptive approaches. This is significant in the sense that - if I parse the paper correctly - this is the first work that considers an adaptive partitioning approach of this kind in the context of optimistic optimization.", "essential_references_not_discussed": "I do not have enough familiarity with the specific literature to assess this.", "other_strengths_and_weaknesses": "* The authors never describe the SequOOL algorithm in detail. Given that this is not just a comparison baseline but an integral part of the proposed method, this makes it hard to understand the contribution for the non-expert already familiar with SequOOL.\n* Apart from that, despite being quite technical, the paper tries to make itself at least somewhat accessible to the non-expert. For instance, I liked the intuition provided in the paragraph right after Definition 2.7 (though I believe there is a typo: eta -> nu).\n* Overall, the empirical results are rather disappointing:\n    * Algorithm 1 does well on a couple of the examples (however, the authors don't provide much intuition for why htat is the case) but is otherwise worse than many baselines, especially in the small-sample regime (anytime performance matters!).\n    * Algorithm 2 does not appear to be evaluated on the synthetic functions (why?).\n    * For the LLM example, while a nice and practical real-world example, it is not clear how meaningful the improvement is compared to the baselines, and the results are from a single replicate - I understand that compute capacity here is a limitation, but it's still just not clear how meaningful the result is.", "other_comments_or_suggestions": "I find the significance and quality of this paper quite hard to judge as it's outside my expertise, so this is a low-confidence vote.", "questions_for_authors": "* For the experiments, it appears that you generate a single A once per function and then run multiple optimization runs, rather than each replicate being over a new embedded subspace (i.e. a new A), is that a correct understanding? This seems like it could cause some bias in the evaluation. It may be good to re-randomize A, that would make the comparison against the non-randomized algorithms more interesting as well.\n* You mention that one possible direction is to \"extend your approach to the case when the function evaluations are noisy\" - I'm curious how that would work; one of the core assumptions of the index function setting is that the function has a narrow ridge structure. If evaluations are noisy, then it appears that the direction of this structure would be quite hard to estimate (in other words, the learned partitioning schemes would not align with it). How would the theoretical results you obtained translate to a noisy setting.", "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": "", "extra_scores": {}}, {"review_id": "fV8jCg9KEH", "reviewer": "Reviewer_k4R6", "summary": "This paper proposes an adaptive partitioning schemes which divides the search domain into a hierarchical subspace tree to reduce search space and enhance optimization performance. The subspace matrix is learned and updated as a hidden layer of neural network surrogate model. Experimental results on several synthetic problems and LLM quantization problems show that the proposed methods surpass the compared baselines.\n\n## update after rebuttal\n\nI keep my score. My final assessment of this paper is 2.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We respond to the reviewer's questions below.\n\n> For each problem instance, the surrogate network should be trained from scratch to obtain the partitioning matrix\n\nWe trained the neural network using the Ray package for hyperparameter tuning. The search space included hidden layer sizes (500, 1000, 2000, 3000), learning rates (log-uniform from $1 \\times 10^{-4}$ to $1 \\times 10^{-1}$), weight decay (log-uniform from $1 \\times 10^{-2}$ to $1 \\times 10^{-1}$), and learning rate step decay with gamma values (uniform from 0.9 to 0.99) and step sizes (500, 1000, 2000). Early stopping was used to prevent overfitting. We will add these details in our revised draft. \n\n> The number of layers M for the LLMs in the experiments is not reported.\n\nThe number of layers $M$ in our experiment is 24. We will clarify this in the revised draft.\n\n> The test synthetic problems included in the experiments are relatively simple, which are mostly unimodal or low conditioning.\n\n> Weakness: the test synthetic problems are relatively simple. The tested problems are mostly unimodal or low conditioning.\n\nWe thank the reviewers for the question! Our rationale in choosing these test functions is from the paper [1]. We choose one test from each of the category to cover different type of optimization challenges. Sphere function belongs to \"Separable function class\", Ellipsoid function belongs to \"Functions with low or moderate conditioning class\". Branin function belongs to \"highly non-linear class\". Rastrigin belongs to \"Multi-modal functions with adequate global structure\". Sum of Different Powers function belongs to \"Functions with high conditioning and unimodal\" class. Also, RESOO [2] was evaluated using the Branin, Rosenbrock function, while HesBO [3] was tested on the Branin, Hartmann-6, Rosenbrock, and Styblinski-Tang functions. Therefore, we included the results of all the baselines on these functions. \n\n[1] Nikolaus Hansen, Steffen Finck, Raymond Ros, Anne Auger. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. [Research Report](https://inria.hal.science/inria-00362633v2) RR-6829, INRIA. 2009.\n\n[2] Qian, Hong, and Yang Yu. \"Scaling simultaneous optimistic optimization for high-dimensional non-convex functions with low effective dimensions.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 30. No. 1. 2016.\n\n[3] Nayebi, A., Munteanu, A. &; Poloczek, M.. (2019). [\"A Framework for Bayesian Optimization in Embedded Subspaces.\"](https://proceedings.mlr.press/v97/nayebi19a.html) Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:4752-4761.\n\n> In Appendix 8, Proposition 8.1, what is the reason of using the top m right singular vectors of the p vectors in the learned weight matrix\n\nProposition 8.1 is valid for any $p$ and we could set the $p$ to be $m$.\n\n> The rows in the estimated A may not be orthonormal, will it affect the optimization performance?\n\nA is estimated from the SVD of neural network weights, hence the rows of estimated A are orthonormal.\n\n> How will the values of the number of dimensions m and integer c in Algorithm 2 affect the performance? Or how to choose a proper value for m and integer c\n\nIn practice, we can choose the value of m to explain a desired percentage (such as 95\\%) of the total variation in the SVD step calculating $\\hat{\\mathbf{A}}$. $c$ is a hyper parameter which is chosen as 5 in our experiments. Larger er $c$ would mean we use more samples for the optimization and lesser samples for the surrogate training. Smaller $c$ would mean we use more samples for surrogate training and less samples for optimization. For a unseen problem we need to perform hyperparameter tuning to find the optimal value for $c$.", "claims_and_evidence": "The authors demonstrate the effectiveness of the proposed methods through theoretical analysis and comparison experiment on synthetic and LLM quantization problems.", "methods_and_evaluation_criteria": "The overall method is to learn a subspace partitioning matrix by fitting a neural network surrogate model and sample solutions from the partitioned subspace which contains the optimal solution. The authors proof the correctness of the proposed method through theoretical analysis.", "theoretical_claims": "The authors provide the detailed proof of the proposed theorems and lemmas in the paper and Appendix.", "experimental_designs_or_analyses": "1) For each problem instance, the surrogate network should be trained from scratch to obtain the partitioning matrix, however, I did not find the surrogate training settings for synthetc problems? The time efficiency for the surrogate training in synthetic problems is not reported.\n\n2) The number of layers M for the LLMs in the experiments is not reported.\n\n3) The test synthetic problems included in the experiments are relatively simple, which are mostly unimodal or low conditioning.", "relation_to_broader_scientific_literature": "1) Black-box Optimization: The proposed methods are developed to solving black-box optimization problems.\n\n2) Surrogate Model: The partitioning matrix is learned by fitting a surrogate model.\n\n3) Large Language Model: In the experiment, the proposed method is applied to solve the LLM quantization problems.", "essential_references_not_discussed": "I didn’t see any essential references not discussed.", "other_strengths_and_weaknesses": "Weakness: the test synthetic problems are relatively simple. The tested problems are mostly unimodal or low conditioning. For simple or unimodal problems the surrogate model could be fitted more quickly and the subspace containing optimum could also be recognized more easily. Testing the methods on multi-modal and high conditioning problems such as COCO BBOB or CEC series benchmarks might enhance the convincingness of the experiments.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1) In Appendix 8, Proposition 8.1, what is the reason of using the top m right singular vectors of the p vectors in the learned weight matrix of the hidden layer as the partitioning scheme instead of setting p=m?\n\n2) The rows in the estimated A may not be orthonormal, will it affect the optimization performance?\n\n3) How will the values of the number of dimensions m and integer c in Algorithm 2 affect the performance? Or how to choose a proper value for m and integer c when optimizing an unseen problem?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces two adaptive partitioning algorithms for optimistic optimization, extending gradient-free algorithms such as SequOOL. The paper proposes a novel approach by bringing adaptivity to the optimistic optimization setting. It provides an interesting theoretical proof. However, reviewers pointed out a few weaknesses, such as a lack of important baselines, limited experimentation, and a lack of important reproducibility information. Based on the rebuttal and the author's commitment to update the paper, I would recommend a weak accept.
Decision: Accept (poster)