Regret Bounds for Noise-Free Cascaded Kernelized Bandits
Authors: Zihan Li
Jonathan Scarlett
Venue: Accepted by TMLR ()

Abstract: We consider optimizing a function network in the noise-free grey-box setting with RKHS function classes, where the exact intermediate results are observable. We assume that the structure of the network is known (but not the underlying functions comprising it), and we study three types of structures: (1) chain: a cascade of scalar-valued functions, (2) multi-output chain: a cascade of vector-valued functions, and (3) feed-forward network: a fully connected feed-forward network of scalar-valued functions. We propose a sequential upper confidence bound based algorithm GPN-UCB along with a general theoretical upper bound on the cumulative regret. In addition, we propose a non-adaptive sampling based method along with its theoretical upper bound on the simple regret for the Mat\'ern kernel. We also provide algorithm-independent lower bounds on the simple regret and cumulative regret. Our regret bounds for GPN-UCB have the same dependence on the time horizon as the best known in the vanilla black-box setting, as well as near-optimal dependencies on other parameters (e.g., RKHS norm and network length).

Published in Transactions on Machine Learning Research (05/2024)
Regret Bounds for
Noise-Free Cascaded Kernelized Bandits
Zihan Li
Keihan nus edu
National University of Singapore
Jonathan Scarlett
scarlett@ccomp.nue edu..s
National University of Singapore
Reviewed on OpenReview: https: // openreview. net/ formn id- oCf ammt
Abstract
We consider optimizing a function network in the noise-free grey-box setting with RKHS function classes, where the exact intermediate results are observable. We assume that the structure of the network known (but not the underlying functions comprising it), and we study three types of struetures: (1) chain: cascade of scalar-valued functions, (2) multi- output chain: cascade of vector-valued functions, and (3) feed-forward network: fully connected feed-forward network of scalar-valued functions. We propose sequential upper confidence bound based algorithm GPN-UCB along with a general theoretical upper bound on the cumulative regret. In addition, we propose non-adaptive sampling based method along with its theoretical upper bound on the simple regret for the Matérn kernel. We also provide algorithm-independee
lower bounds on the simple regret and cumulative regret. Our regret bounds for GPN-UCB have the same dependence on the time horizon as the best known in the vanilla. black-box setting, well near-optimal dependencies other parameters (e.g., RKHS norm and network length).
1 Introduction
Black-box optimization of an expensive-lo-evaluuae function based on point queries is a ubiquitous problem in machine learning. Bayesian optimization (or Gaussian process optimization) refers to a class of methods using Gaussian processes (GPs), whose main idca to place a prior over the unknown function and update the posterior according to point query results. Bayesian optimization has a wide range of applications including parameter tuning (Snoek al. 2012), experimental design (Griffiths and Hernández-Lood Lobato 2020). and robotics (Lizotte al. 2007). While function evaluations are noisy in most applications, there are also scenarios where noise-free modeling can be suitable, such simulation (Nguyen et al. 2016). goal-driven dynamics learning (Bansal et al. 2017), and density map alignment. (Singer and Yang 2023
In the literature on Bayesian optimization, the problem of optimizing real-valued black-box function is usually studied under two settings: (1) Bayesian setting: the target function is sampled from a known GP prior, and (2) mon-Bayesian setting: the target function has low norm in reproducing kernel Hilbert space (RKHS).
In this work, consider setting falling "in between" the white-bon setting (where the full definition of the target function is known) and the black-box setting, namely, grey-box setting in which the algorithms can leverage partial internal information of the target function beyond merely the final outputs or even slightly modily the larget function (Astudillo and Frazier (021b). Existing grey-box optimization methods exploit internal information such as observations intermediate outputs for composite functions (Astudillo and Frazier 2019) and lower fidelity but faster approximation of the final output for modifiable functions (Huang et (2066.. Numerical experiments show that the grey-box methods significantly outperform standard black-box methods (Astudillo and Frazier 2021b)

---

Published in Transactions on Machine Learning Research (05/2024)
Though any real-valued network can be treated as single black-box function and solved with classical Bayesian optimization methods, we explore the benefits offered by utilizing the network structure information and the exact intermediate results under the noise-free grey-box setting. Several practical applications of the cascaded setting (c.g., alloy heat treatment and simulation) are highlighted in Appendix A
1.1 Related Work
Numerous works have proposed Bayesian optimization algorithms for optimizing a single real-valued black- box function under the RKHS setting. For the noisy setting, (Srinivas et al. 2010 Chowdhury and Gopalan
2017 Gupta et al. 2022) provided a typical cumulative regret O(vThr), where T is the time horizon, TT is the maximum information gain associated to the underlying kernel, and the Ō(.) notation hides the poly- logarithmic factors. Recently, (Camilleri et al. 2021 Salgia et al. 2021 Li and Scarlett 2022 achieved cumulative regret Ö(TTTT), which nearly matches a algorithm-independee exponential and Matérn kernels (Scarlett et al.,
lower bounds for the squared Cai and Scarlett 2021). For the noise-free setting, [Bull 2011) ) achieved nearly optimal simple regret O(T- for the Matérn kernel with smoot
2017
This result implies a two-batch algorithm that uniformly selects Tofa points in the first batch and repeatedly picks the returned point in the second batch, has cumulative regret O(Tv44). In addition, (Lyu et al. 2019) provided deterministic cumulative regret O(vTTr), with the rough idea being to substitute zero noise into the analysis of GP-UCB (Srinivas et al. 2010). Recently, (Salgia et al.] 2023 proposed batch algorithm based on random sampling, attaining cumulative regret ((T1-v/d) when < d and O(poly T)) when V 2 d.
Mcanwhile, several Bayesian optimization algorithms for optimizing a composition of multiple functions under the noise-free selting have been proposed. (Nguyen al. 2016) provides method for cascade Bayesian optimization; (Astudillo and Frazier 2019) studies optimizing composition of black-box function and known theap-to-evaluate function; and (Astudillo and Frazier 2021a) studies optimizing network of functions sampled from a GP prior under the grey-box setting. Both (Astudillo and Frazier 2019) and (Astudillo and Frazier 2021a) prove the asymptotic consistency of their expected improvement sampling based methods.
The most related works to ours are (Kusakawa al. 2022) and (Sussex et al. 2023). Kusakawa et al. 2022 introduces two confidence bound based algorithms along with their regret guarantees for both noise- free and noisy settings, well an expected improvement based algorithm without theory. (Sussex et al., 2023 considers directed grey-box networks representing causal structure, and proposes an expected improvement based method with regret guarantee. A detailed comparison regarding problem setup and theoretical perfor- mance is provided in Appendix K In short, we significantly improve certain dependencies in their regret for a UCB-type approach, and we study two new directions non-adaptive sampling and algoritam-inddepedeen
lower bounds that were not considered therein (summarized Section 1.2).
For function networks with layers, our cumulative regret bounds exprossed in terms of
T
Ex max se/m] Ai.
max
o (2+).
where x0 and o(2(() denote the domain and posterior standard deviation of the i-th layer respectively. This is a term for general layer-composed networks associated to domains 2²11) 2(,),...,,2'0 2 and kernel k. When m = 1, the term maxxx...xxxx* DT" (x;) often appears in the cumulative regret analysis of
classic black-box optimization (Srinivas et al. 2010 Lyu al. 2019 Vakili 2022). Explicit upper bounds
on Er will be discussed in Section 3.4
1.2 Contributions
We study the problem of optimizing an m-layer function network in the noise-free grey-box setting, where the exact. intermediate results are observable. We focus three types of work structures: (1) chain:
2

---

Published in Transactions on Machine Learning Research (05/2024)
Lower bound
Q(B(cL))-1122->
Upper bound (chains)
O(2TBL"-123
O(2
Upper bound (multi-output chains)
OL "-
O BL m (T) u/ thmax)
Upper bound ffood-forward networks)
m V mL ΣT)
0 D22m BL m 1 Muuux
Table 1:
Summary of cumulative regret bounds for the Matérn kernel when d 2
and T
(((((1))m-1)d/))) for some ((1). Here (c) indicates the behavior when conjecture of Vakili 2022
the black-box setting holds.
(()
(()
x
f(
fim
(
((m)
d= di
Am=i
Figure 1: A function network of layers with input x and output y.
cascade of scalar-valued functions, (2) multi-output chain: a cascade of vector-valued functions, and (3)
feed-forward network: fully connected feed-forward network of scalar-valued functions. Then:
We propose fully sequential upper confidence bound based algorithm GPN-UCB along with its upper bound on cumulative regret for cach network structure. Our regret bound significantly re- duces certain dependencies compared to (Kusakawa el al. 2022). in particular showing that their dependence on a "posterior standard deviation Lipschitz constant" can be completely removed.
We introduce a non-adaptive sampling based method, and provide its theoretical upper bound on the simple regret for the Matérn kernel.
We provide algorithm-inndepeneett lower bounds on the simple and cumulative regret for an arbi- Irary algorithm optimizing any chain, multi-output chain, feed-forward network associated to the Matérn kernel. In broad regimes of interest, these provide evidence or even proof that upper bounds near-optimal.
While the goals of this paper are essentially entirely theoretical, we show in Appendix L that (slight variations of) our algorithms can be effective in at least simple experimental sccnarios.
Let d denote the dimension of the domain, dmax denote the maximum dimension among all the m layers, and D2.m denote the product of dimensions from the second layer to the last layer. With > O restricting the mdgnitude and smoothness each layer and L restricting the slope of each layer, a partial summary of the proposed cumulative regret bounds for the Matérn kernel with smoothness 2 when d 2 and T (((B(cL)m-Iddd)) for @(1) is displayed in Table From this table, we note the following:
The upper and lower bounds share the same BI. BIm-1TTI-//4 dependence when d= dmax and simul- laneously conjecture of (Vakili 2022 holds.
Even without such conjecture, the dependence on Ex is preciscly that given in statc-of-tho-art bounds for the vanilla black-box setting (Vakili 2022), and rigorous upper bounds are known.
See Section 3.4 for further details on the conjecture and rigorous bounds.
To our knowledge, we are the first to attain provably near-optimal scaling (in broad cases of interest), and doing so requires both improving the existing upper bounds and attaining novel lower bounds. A full summary our thcoretical results provided
Appendix J Perhaps our most restrictive assumption is noise-free observations, but we believe this is a crucial stepping stone towards the noisy setting (as was the case with regular black-box optimization, e.g., (Bull 2011
3

---

Published in Transactions on Machine Learning Research (05/2024)
2 Problem Setup
We consider optimizing a real-valued grey-box function on x= = [0, 1j based on noise-free point queries.
As shown in Figure [
the target function is known to be a network of m unknown layers f(9 with i [m]]
In general, for any input EX the network y has x(2) = x and
x(++1) = (x())
for i E [m - 1],
リ= 9(x) f (x (x(
ER,
where x(1) has dimension d, for cach [m]. The domain of f(l is X00 and the range of f() is x For any x(0), there exists x E such that x(1) z.
We aim to find x arg x g(x) based sequence of point queries up to time horizon T. When we query with input x, at time step i, the intermediate noise-free results x, ,...,,, (m) and the final noise-free
output y are accessible. We measure the performance as follows:
Simple regret: With x; being the additional point returned after T rounds, the simple regret is defined as r = g(x") - ((x;));
Cumulative regret: The cumulative regret incurred over T rounds defined as Rr Σle P with r, = g(x)..
2.1 Kernelized Bandits
We assume 9 is a composition of multiple constituent. functions, for which we consider both scalar-valued functions and vector-valued functions based on a given kernel. For a scalar-valued kernel and a known conslant B O, we consider scalar-valued functions that lie in Hz (B), the reproducing kernel Hilbert space (RKHS) associated smoothness O. Similarly, for operator-valued kernel T and known constant B > O, consider vector-valued functions in Hr(B), the RKHS corresponding to I with norm at most B. More details on RKHS and kaatérn are given in Appendix B
with norm most B. In this work, we focus on the Matérn kernel Matéé with
2.2 Surrogate GP Model
As is common in kernelized bandit problems, our algorithms employ a surrogate Bayesian GP model for f E (B). For prior with zero mean and kernel k, given a sequence of points (x),...,X.) Xt) and their noise- free obscrvations y: (y1..... Me) up to time t, the posterior distribution the function is a GP with mean and variance given by (Rasmussen and Williams 2006)
(x(x)= = kx(x)" (x, y: (x)) - k(x,)) (x(x) (x),,
(1)
(2)
where k, (x) = [x x; ) E R(x1 and K; 1K(x,,;)){ E Rxxt, The following lemma shows that the postcrior confidence region defined with parameter B is always detorministically valid.
Lemma 1. (Kanagawa al. 2018 Corollary 3.11) For f E (B))),, let px(x) and and (x)2 denote the posterior mean and veriance based L points (XI,..., x1) and their noise-free observations (y1...., M.) using 1 and
2 Then, it holds for all x E X that
ff(x) (x() S (x,
We also impose surrogate GP model for functions in HB). The posterior mean and covariance matrix based on (Xi....,xy xx) and the noise-free observations Yú = (y1....,y:) are (Chowdhury and Gopalan 2021
[x(x) Gx(x)
(3)
T,(x,x) T(x,x) G;
(4)
Note the equivalent notation x and di

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm GPN-UCB (Gaussian Process Network Upper Confidence Bound)
for ( 1,2,..... T do
Select X2 <- arg maxxex UCB(-1(X) 3:
Oblain observations x; (m) and Dr-
Compute UCB, using
(1) 19 based {xs ..... x x!") MaJa=1
(11)
where G+(x) = [x x;)li=1 E Ratxn G. [T(x;, x))l.=== E Rutxat and Y, [yili=z E |R With || l|a denoting the spectral norm, the following lemma provides a deterministic confidence region.
Lemma 2. For f E (B)), px(x) and Tx(x, x) denote the posterior mean and variance based on t points (x)....,X,) and their noise-free observations (yi.....ye) using 3 and 14. Then, it holds for all E X
that
lf((x) - (x()ll22 & (x|T,(x,x)113
The proof is given in Appendix D
2.3 Lipschitz Continuity
We also assume that each constituent function in the network g is Lipschitz continuous. For a constant L > 1, we denote by F(L) the of functions such that
F(L) = (f: llf(x)) - f(x')ll llaa s L|| x' x'12. Vx, x'},
where L is called the Lipschitz constant. This is mild assumption, (Le et al. 2022) has shown that Lipschitz continuity is guarantee for functions in (B( for the commonly-usee squared exponential kernel and Matérn kernel with smoothness > 1.
2.4 Network Structures
In this work, we consider three types of network structure; example figures are included in Appendix C
Chain: For scalar-valued kernel k, chain is cascade of scalar-valued functions. Specifically, d 2 1, d2 d3 dm 1, and f(0 ( for each E [m].
Multi-output chain: For operator-valued kernel F, multi-output chain is cascade of vector- valued functions. Specifically, d; 2 1 and f()) E ( for each i E [m].
Foed-forward network: For a scalar-valued kernel k, a feed-forward network is a fully-conneeted feed-forward network of scalar-valued functions: dc > and (() (z)) with f(t.)) e (B) ( ((L) for each E [m]]. j [di+1].
In each case, the network is scalar-valued with the dimension of the final output being dm+1 = 1.
3 GPN-UCB Algorithm and Regret Bounds
In this section, we propose fully sequential algorithm GPN-UCB (see Algorithm 1 for chains, multi-output chains, and feed-forward networks. The algorithm works with structure-specific upper confidence bounds. Similar to GP-UCB for scalar-valued functions (Srinivas et al. 2010), the proposed algorithm repeatedly queries the point with the highest posterior upper confidence bound, while the posterior upper confidence bound UCB,-1 used here is computed based on not only the historical final outputs {y. but also the
(2) intermediate results (x(2² (xe",..... ...., (-1

---

Published in Transactions on Machine Learning Research (05/2024)
3.1 GPN-UCB for Chains
A chain is cascade of scalar-valued functions. For each E [ma] we denote by P4 and oi the posterior
(6)
(3)
mean and standard deviation of f(9 computed using ① and (2 based on {x Xx (++)) y Then, based on
Lemma | the upper confidence bound and lower confidence bound of f() based on exact observations
are defined follows:
UCB! (z) 14) (z) + Boi (z),
(5)
LCB, (z) (0) (z) (z).
(6)
Since f00 E F(L,, we have for any 2, z' that
UCB ( (z') (2.) + 1. - 2| 2 (z) + L/ 2'12 (2).
(7)
LCB, (1) (z') L z'112 v (z)) L| z'112 S (z)
(8)
It follows that
(1) (z) = min (UCB, (1) (z') + T.I1 z =/112); UCB,
(9)
LCB, (z) max (LCB, (z') - L z 112)
(10)
z'
are also valid confidence bounds for (z). UCB (z) the lower envelope of a collection upper bounds for (z), which can be obtained by considering multiple values of (7) Then, since g is a cascade of f for any imput x, we can recursively construct a confidence region of ((++1) based on the confidence
region of x(1), and the following UCB for g(x) is valid:
(C)
max UCB (z),
(11)
(x)
where A ( (x) denotes the confidence region of (0;
11" {x)
4 (1+1)
(x) min
LCB, (z), max
UCB
(z)
x (x)
x (x)
for E [m [m-11 1]. The theoretical performance of Algorithm D for chains using the upper confidence bound in 11 is provided in the following theorem.
Theorem (GPN-UCB for chains). Under the setup of Section 2 given B > 0 and L 1, scolar-valued kernel k, and choin g = f(()) o f(mm1) o ....a o. f(1) with f(l) E Hx ()(B) for each i [m], Algorithm
achieves
Rr < 2
where Ex max iE[m] 2i.... Zy (X
max
Eie (1) 0- (2:).
3
The proof is given in Appendix F.1 and upper bounds on Σr will be discussed in Section 3.4 Regardless
of such upper bounds, we note that. BEr serves as noise-free regret bound for standard (Vakili 2022), and thus, the key distinction here is the multiplication by -m1 See Section for a study of the extent to which this dependence is unavoidable.
GP optimization
Note the equivalent notation x(1) x and x(m+1) = y.
IIn this definition and analogous definitions below, (4) is defined according the hypathetical sampled points x((

---

Published in Transactions on Machine Learning Research (05/2024)
We note that GPN-UCB may be difficult to implement eractly in practice; in particular: (i) Since xr(2) , (m)) are not known, and (10) are computed based on all z' E Rd;; (ii) Recursively com- puting (11 is also resource consuming. However, these problems can be alleviated by (i) only considering z' sufficienlly close to z (since distant oncs should have no impact) and (ii) replacing each confidence region by its intersection with a fixed discrele domain (e.g.: a finite grid). In Appendix we show that such a practical variant can be effective, at least simple experimental scenarios.
3.2 GPN-UCB for Multi-Output Chains
A multi-output chain is a cascade of vector-valued functions. For any imput z of the multi-output function f()), we define the confidence region of f ((( (z) as
c (z) = M c (2,z'),
(12)
where
(2) (4 c (2,2') (v+ w e (z'), || S -|| z'' 2'112].
1 (2) + u: u. R ||ulle = (2,
(2, 1/2
(13)
(14)
Lemma shows that c. (z') is a valid deterministic confidence region for (z)). Assuming f E F(L), (2)) + w w E [d4+1, ||w||2 _ L| - z' 2/122 containing all the points satisfying the Lipschitz property is valid confidence region for (z), and therefore its superset c.¹) (z, x') is also a valid confidence region for (z). Since (z) must belong to the intersection of all its confidence regions, (( is again a valid deterministic confidence region for (z). Hence, noting that clT²) is subset of R (unlike the vector-valued layers), the upper confidence bound for g(x) for any input x based on t observations is
UCB.(x)
max c
c)
(z),
(15)
xEA(") (x)
where (x) denotes the confidence region of (() based on i observations such that
A T (x) = {x}
A (++1) (x) (x) = U (2)
for i E [m - 1].
(16)
(x)
The cumulative regret achieved by Algorithm for multi-output chains using the upper confidence bound in 15 is provided in the following theorem.
Theorem 2 (GPN-UCB for multi-oulput chains). Under the selup of Section operator-enlued kernel T, and multi-oulput chain f(m) f(mm1) for each i E [m], Algorithm achieves
2 given B > and L > 1, with f() Hr(B) n F(L)
RT S 55th 5L
where Σ
max /E|m] 21.......
EL (1 2, 21 11
The proof is given in Appendix F.2
Remark Fix x())2()) ....,. (m)) with dimension d1,d2, de...., dm 2 1 respectively. For I(..)) k(.-))
with & being a scalar-valued kernel and I being the identity matrix of size dit1, it follows from Lemma (see Appendix E that ΣT = Ex-
The upper bound DL for general operator-valued kernels will be discussed in Section 3.4

---

Published in Transactions on Machine Learning Research (05/2024)
3.3 GPN-UCB for Reed-Forward Networks
In the ferd-forward network structure, (() = ( (x)] and each ((J E He(BB) is a scalar-
valued function. Similar to (9] and (10 with (1-9) (z) and of (2)² denoting the posterior mean and variance
of (z) using and the following confidence bounds on (z) based on {(x: Xs valid:
(0) (++1)))
) are
UCB, (15) (2) min(UCB (z)) + L/ z'112),
LCB, (1)) (0)((((()) (z) max(LCB; (1.1) (z') L z' z2122),
(17)
x'
where
(CB())()) =1 (15) + Bo, (1-) (2),
LCB( = p4 (1.5) (z) Bo! (z).
(18)
Then, the upper confidence bound of g(x) based observations is
UCB:(x)= DEA
UCB, (m.1) (z).
(19)
where
(x) =(x},
4 (1-10) (x)
min LCB
(i.f)
(z),
max
UCB (15) (z)
for i E [m - 1],j E [d++]],
! (x)
2EA!"
A (x) (6
(1.1)
(x)
A, (i.de) (x)
for i E [m]]
(20)
The following theorem provides the theoretical performance of Algorithm 1 for feod-forward networks using the upper confidence bound in 19h.
Theorem 3 (GPN-UCB for feed-forward networks). Under the setup of Section g
given B > 0 and L 1, a scalar-valued kernel k, and feed-forwar network g = f(m) o f(m-1)o.... (()) with ( = ((())) and f(is)) E HB(B) F(L) for each E [m],j E [di+1], Algorithem achieves
R1 S 2 / DD BL m-
where D2.m = 1l di and Vi
max mE|m] 2...... (v)
max
ΣT 0-1 (Zt).
The proof is given in Appendix
Since (f.1) in the foed-forward network setting is computed using 2 which exactly the same as how ((i) is computed in the chain setting, despite the slightly different superscripts, the En term in Theorem 3 represents the same quantity in Thcorem 1 (depending on 2211) (2) ( p(m)). In particular, when d2 =... dm =1 Theorem recovers Theorem
3.4 Upper Bounds En and ΣF
A simple way to establish upper bound on the Er term in Theorem Remark 1 and Theorem to essentially set the noise term to be zero in a known result for the noisy setting. For the scalar-valued function (GP bandit) optimization problem under the noisy setting, most existing upper bounds on cumulative regret are expressed in terms of the maximum information gain corresponding to the kernel defined as N maxx,....x. 1/2 log det + X - -k,), for a free parameter 0 (Srinivas et al. 2010), and (Srinivas et al.
2010 has shown that the of posterior variances in the noisy setting satisfies Σ (x,) O(Tr).

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 2 Non-Adaptive Sampling Based Method
1: Choosing [x,)ø=1 such that dr = =
Obtain observations {x&s (2) ,-.., :y4 8=s-s=1-
(m)
3: Compute μ based on (xg ,...,, X5 (m)
Output: Xi- = arg maxxex 12)(x).
inequality, we have ËT = (VTTTT). An existing upper bound on 7T for the Matérn kernel with dimension and smoothness // on a fixed compact domain is 7T Matérn Ö 2 (akili et al. 2021). In our setting, a simple sufficient condition for this bound to apply is that dmax maxie(m] di, L, and are constant, since then the Lipschitz assumption implies that each domain 211),, x(2), ...... ,..,,..... x((m) is also compact/boune bounded.. More gencrally, we believe that uniformly bounded domains a mild assumption, and when it holds, the bound M+ddmax
where xx(2 = k(xx x) k, (x) - (x)). Using ox I ox(x) and the
Er O simplifies to Ey = (T
In addition, (Vkiili 2022)
provides the following conjecture on the upper bound on Ey for the Matérn
kerne F
O(T1-v/dman
when dmax > V, when dmax when dmax < V.
Matéra
OlogT) 0(1)
We will discuss in Section D how if this conjecture is true, we can deduce the near-optimality of GPN-UCB for the Matérn kernel. We note that (Vakili, 2022) primarily conjectured on vanilla noise-free cumulative regret by conjecturing an upper bound on Er. Recently, (Salgia et al.) 2023) used a random sampling algorithm with elimination to atlain the conjectured cumulative regret, while leaving open the conjecture on Σy and whether GP-UCB attains the same regret (though arguably further increasing its plausibility).
For an arbitrary operator-valued kernel I X'x X + R=x and free parameter X, the maximum information gain is defined as of = ....x......xx 2 log dei + - (Chowdlury and Gopalan 2021). (Chowdbury and
Gopalan 2021 has shown that Σ 1 x,)1 = O(TF), and therefore ET O( (TF) by similar reasoning to above.
4 Non-Adaptive Sampling Based Method
In this section, we propose simple non-adaptive sann-adlliiieemmpiingg based method (see Algorithm 2 for each structure, and provide the corresponding thcoretical simple regret for the Matérn kernel. For set of T sampled points (x.)==1> its fill distance is defined as the largest distance from a point in the domain to the closest sampled point 87 = maXxex min ||x-x,lla /Wendland] 2004).. Algorithm 2 samples points with d7 = O For X' = [0, 1] a simple way to construct such a sample is to use a uniform d-dimensional grid with step size 11d/ The algorithm observes the selected points in parallel, computes a structure-specific "composite mean" 2 (to be defined shortly) for the overall network g, and returns the point that maximizes ud.
The composite posterior mean of gxx with chain structure is defined as
(x) (H(m)
uT
(m o... ( (xx)
(21)
(i) where pl denotes the posterior mean of (+) computed using I based on {xx(", x! ( for each i [m] Then, the following theorem provides the theoretical upper bound on the simple regret of Algorithm 2
4In more detail, maxzi....ry ΣT ( where the maximum is over an arbitrary sequence of points (not necessarily those of GP-UCB). For (.i...., ..7)) where the maximum is achieved, (Vkilli 2022 conjectures that (xf....,?}) are roughly uniformly distributed across the domain. The desired upper bound on 6 (and, turn, our Fey) is derived by assuming that this conjecture holds.
Vakili 2022
shows that an analysis of GP-UCB gives rise to the quantity O
9

---

Published in Transactions on Machine Learning Research (05/2024)
using 21
Note that the notation Ō() hides poly-logarithmic factors with respect to the argument, e.g.: ((VT)= OVTT. (log (T)()) and Õ(2*) O(2 n n.)).
Theorem (Non-adaptive sampling method for chains). Under the setup of Section 2 given B ( kaaatrnn with smoothness v, and a chain g = f(m) fi f(m=1) o... o f(t) with f()) E (z(B) for each E [m], have
When v S 11, Algorithm
achieves
r = m 1 ld);
When 1, Algorithm achieves
7 ( max (BL gl+0te24... L Pa)))
The proof is given in Appendix G.1 and the optimality will be discussed in Section When 1, the simple regret upper bound takes the maximum of two terms. The first term has smaller con- stant factor, while the second term has smaller T-dependent factor. By taking the highest-order con- stant factor and the highest-order T-dependent factor, we can deduce the weaker but simpler bound ri O(BI+tte* to""" L "'""'T T-d/d).
We also consider two more restrictive cases, where we remove the assumption of = @(L), but have additional assumptions on as follows:
Case We additionally assumne that / o... o.....phh uT (x*) x(++1) and py o.. o po (x+)) E x((41)
(x²)
for all E [m 1m-1], 1].
Case We additionally assume that all the domains x²0 are known. Defining
(z) arg min
114 - 2¹1,
x'
slightly modify the algorithm to return
x = arg max (pf ... fff) (xx).
xEX
Remark 2. Under the assumptions of either Case Case 2, Algorithm achieves for chains that
0(BI.--17-11/)
when < 1, when v/ >
r
(22)
The proof is given in Appendix G.2
The composite posterior means and simple regrel upper bounds for multi-output chains and leed-forward networks are provided in Appendix G.3 and Appendix respppcccttil,, where the simple regret upper bounds are stated only for the case that the domain of cach layer is hyperrectangle. Removing this restrictive assumption is left for future work.
5 Algorithm-Independeri Lower Bounds
In this section, we provide algorithn-independen lower bounds on the simple regret and cumulative regret for any algorithm optimizing chains, multi-output chains, or feed-forward networks for the scalar-valued kernel Matér or the operator-valued (Matém((s-)) KMatém II with smoothness
Theorem 5 (Lower bound on simple regret). Fir (0, 21, sufficiently large B 0, k kMatérns and
T Matéra with smoothness 2 1. Suppose that there exists algorithm. (possibly randomized) that
10

---

Published in Transactions on Machine Learning Research (05/2024)
achieves average simple regret B[r9] I after T rounds for any m-layer chain, multi- multi-output chain, or feed- forward network on [0, 1] with some I = ( Then, provided that B is sufficiently small, it is necessory that
T = 2
(((
) d/v
c
for some (1).
The proof is given in Appendix H. and the high-level steps are similar to Bull 2011p, but the main differences are significant. For each structure, we consider a collection of M hard functions g . 9MM), where each Oj is obtained by shifting a base function J of the specified structure and cropping the shifted function into [0, 1já. Then, we show that there exists a worst-case function in 9 with the provided lower bound. Different from (Bull 2011), the hard functions we construct here are function networks. We define the first layer as "ncedle" function with much smaller height and width than (Buli) 2011). For subsequent layers, we construct function with corresponding RKHS norm such that the output is always larger than the input. As consequence, the "needle" function gets higher when being fed into subsequent layers, and the composite function is "needle" function with some specified height but much smaller width.
Remark 3. It will be evident from the proof that the constant e is always strictly less than 1. Idcally, we would like it to be close to so that (cL)" is similar to I.", with the latter quantity appearing in our upper bounds. It turns out that c can indeed be arbitrarily close to 1 in most cases. Specifically, we will show in Appendix H..5 that when v >> 1 and e is small enough, e simply becomes the ratio of the minimum slope to the maximum slope the kernel function (as a function of the Euclidean distance ||x [|x-x'|]) on [u- ū, u 7. where u and ü can be arbitrarily small. Since the squared exponential (SE) and Matérn kernels have no sharp changes as function of ||x =x'll, this ensures that e can be arbitrarily close to one when v > 1 and is small. In Appendix H.5 will also demonstrate cases where is not too small (e.g., > 0.93) even when the abooe-mentiones quantities (u, ū) are moderate (e.g., (u, ū) (0.5, 0.3)).
The lower bound simple regret readily implics the following lower bound cumulative regret.
Theorem 6 (Lower bound on cumulative regret). Fir sufficiently large B > k kaatrrns and l' Mozérn with smoothness 2 1. Suppose that there erists algorithm (possibly randomized) that achieves average cumulative regret R[] after T rounds for any m-layer chain, mulli--ulpuut chain, ferd-forward network on [0, 1]d with some L = O(B). Then, it is necessary that
E[Rt] = (2(min(T. B(c.)) ((cL))=-1(---//)) when d > v,
Q min (T, (B(cL)m-1)a -//)))))))))))))
when d S v,
for some e = (()).
The proof is given in Appendix !
6 Comparison of Bounds
In this section, compare the algorithmic upper bounds of GPN-UCB (Algorithm I and non-adaptive sampling (Algorithm 2 to the algorithmic-indeeeddee conditioned on the conjecture of (Vakili 2022) being true, but we re-iterate that even without this, any Σn dependence still matches the vanilla setting, and has known rigorous upper bounds as detailed in Section 3.4 A table summarizing the regret. bounds for the Matérn kernel is provided Appendix J
lower bounds in Section 5 We present our discussion
For GPN-UCB, the cumulative regret upper bound for chains (Theorem matches the lower bound (The- orem 6 up to 2n factor when d d21 2 1 and T = (((((cL)"=-1)11)) The upper bound for multi-output chains (Theorem 2 is similarly optimal (up to 5th term) when dmax d ソ 1, while there is always an D(D22,. gap for the T-independent factor of foed-forward networks (Theorem When d < and T (B((L))) m- 1 the cumulative regret lower bound for all the three structures is ((BB(e)))=I1d)/)))
11

---

Published in Transactions on Machine Learning Research (05/2024)
while the upper bound always contains O(BL"=!) factor; hence, the terms behave similarly but some gaps still remain.
We expect that the discrepancies for multi-output chains and feed-forward networks are due to the looseness of the proposed lower bound. Since the hard functions G used analysis always produce single-entry vector output for intermediate layers, for fixed value B, there might exist worse hard function network with more nonzero entries for intermediate outputs and a probably higher final regret.
For non-adaptive sampling, when == 1, the upper bound for chains (Theorem matches the lower bound (Theorem 5) to a cmh- factor. When >> 1, Theorem 4 shows that the simple regret upper bound takes the maximum of two terms, where the first term has matched T-dependent factor. However, both terms have a larger T-independent factor than the lower bound when > 1; this arises due to magnifying the uncertainty from each layer to the next.
7 Conclusion
We have proposed an upper confidence bound based method GPN-UCB and a non-adaptive sampling basod method for optimizing chains, multi-oulput chains, and feed-forward networks the noise-free grey-box setting. Our regret bounds significantly improve certain dependencies compared previous works, and we provide lower bounds that near-matching in broad cases of interest. An immediate direction for future work is explore noisy extensions of our algorithms (as well as lower bounds), idcally attaining analogous improvements over existing works (Kusakawa el. al. 2022 Sussex el. al. 2023 as those that we allained in the noiseless setting (as discussed in Appendix K
Acknowledgment
This work was supported by the Singapore Ministry of Education Academic Research Fund Tier 1 under grant number A- 4-8000872-00-00.
12

---

Published in Transactions on Machine Learning Research (05/2024)
References
Astudillo, R. and Frazier, P. (2019). Bayesian optimization of composite functions. In Int. Conf. Mach. Learn. (ICML).
Astudillo, R. and Frazier, P. (2021a). Bayesian optimization of function networks. In Conf. Neur. Inf. Proc. Sys. (NeurIPS).
Astudillo, R. and Frazier, P. I. (2021b). Thinking inside the box: A tutorial grey-box Bayesian optimiza- tion. In IEEE Winter Simulation Conference (WSC).
Bansal, S., Calandra, R., Xiao, T., Levine, S., and Tomlin, C. J. (2017). Goal-driven dynamics learning via Bayesian optimization. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 5168 5173. IEEE.
Bull, A. D. (2011). Convergence rates of efficient global optimization algorithms. J. Mach. Learn. Research, 12(10).
Cai, X. and Scarlett, J. (2021). On lower bounds for standard and robust Gaussian process bandit optimiza- tion. In Int. Conf. Mach. Learn. (ICML).
Camilleri, R., Jamieson, K., and Katz-Samuels, J. (2021). High-dimensional experimental design and kernel bandits. In Int. Conf. Mach. Learn. (ICML).
Carmeli, C., De Vito, E., and Toigo, A. (2006). Vector valued reproducing kernel Hilbert spaces of integrable functions and mercer theorem. Analysis and Applications, 4(04):377-408.
Chowdhury, S. R. and Gopalan, A. (2017). On kernelized multi-armed bandits. In Inl. Conf. Mach. Learn. (ICML).
Chowdhury, S. R. and Gopalan, A. (2021)- No-regret algorithms for multi-task Bayesian optimization. Tn Int. Conf. Art. Intel. Stats. (AISTATS).
Drusvyatskiy, D. and Paquette, C. (2019). Efficiency minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178:503 558.
Griffiths, R.-R. and Hernández-Lobato, J. M. (2020). Constrained Bayesian optimization for automatic chemical design using variational auloencoders. Chemical Science, 11(2):577-58) 586.
Gupta, S., Rana, S., Venkatesh, S., et al. (2022). Regret bounds for expected improvement algorithms in Gaussian process bandit optimization. In Tnl. Conf. Art. Intel. Stats. (AISTATS).
Huang, D., Allen, T. T., Notz, W. I., and Miller, R. A. (2006). Sequential kriging optimization using multiple-fidelity evaluations. Structural and Multidisciplinary Optimization, 32(5))369-333) 382..
Kanagawa, M., Hennig, P., Sejdinovic, D., and Sriperumbudur, B. K. (2018). Gaussian processes and kernel methods: review on connections and equivalences. attps://arxiv..e wwwiivioor///bb fobs///8000000 0278022
Kusakawa, S., Takeno, S., Inatsu, Y., Kutsukake, K., Iwazaki, S., Nakano, T., Ujihara, T., Karasuyama, M., and Takeuchi, I. (2022). Bayesian optimization for cascade-type multistage processes. Neural Computation, 34(12):2408 2431.
Loe, M., Shekhar, S., and Javidi, T. (2022). Multi-scale zero-order optimization of smooth functions in an RKHS. In IEEE Int. Symp. Inf. Theory (ISIT).
Li, Z. and Scarlett, J. (2022). Gaussian process bandit optimization with few batches. In Int. Conf. Art. Intel. Stats. (AISTATS).
Lizotte, D., Wang, T., Bowling, M., and Schuurmans, D. (2007). Automatic gait optimization with Gaussian process regression. In Int. Joint Conf. Art. Intel. (IJCAT).
13

---

Published in Transactions on Machine Learning Research (05/2024)
Lyu, Y., Yuan, Y., and Tsang, I. W. (2019). Efficient batch black-box optimization with deterministic regret bounds. https:// https///axvv..////iia /005///b0/99950011...
Nguyen, T. D., Gupta, S., Rana, S., Nguyen, V., Venkatesh, S., Deane, K. J., and Sanders, P. G. (2016).
Cascade Bayesian optimization. In Aust. Joint Conf. Art. Intel. (AJCAT).
Rasmussen, C. E. and Williams, C. K. T. (2006). Gaussian processes for machine learning. MIT Press.
Salgia, S., Vakili, S., and Zhao, Q. (2021). A domain-shrinking based Bayesian optimization algorithm with order-optimal regret performance. In Conf. Neur. Inf. Proc. Sys. (NeurIPS).
Salgia, S., Vakili, S., and Zhao, Q. (2023). Random exploration bayesian optimization: Order-optimal regret and computational efficiency. https:/ /atpaaawiioo//////a/////// abbs/ 0tbs/2231.11133 15351.
Scarlett, J., Bogunovic, I., and Cevher, V. (2017). Lower bounds on regret for noisy Gaussian process bandit optimization. In Conf. Learn. Theory (COLT).
Singer, A. and Yang, R. (2023).
Alignment of density maps in Wasserstein distance.
https://arxivvorgg/ wwwpdiiworg/bbs/////ooo/ hbss/2355.12310.
Snoek, J., Larochelle, H., and Adams, R. P. (2012). Practical Bayesian optimization of machine learning algorithms. In Conf. Neur. Inf. Proc. Sys. (NeurIPS).
Srinivas, N., Krause, A., Kakade, M., and Seeger, M. (2010). Gaussian process optimization in the bandit setting: No regret and experimental design. In Tnl. Conf. Mach. Learn. (ICMT..
Sussex, S., Makarova, A., and Krause, A. (2023). Model-based causal Bayesian optimization. In Int. Conf. on Learn. Repr. (ICLR).
Vakili, S. (2022). Open problem: Regret bounds for noise-free kernel-based bandits. In Conf. Learn. Theory (COLT).
Vakili, S., Khezeli, K., and Picheny, V. (2021). On information gain and regret bounds Gaussian process bandits. In Int. Conf. Art. Intel. Stats. (AISTATS).
Wang, M., Fang, E. X., and Liu, H. (2017). Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-ves value functions. Mathematical Programming, 161:419-449.
Wendland, H. (2004). Scattered data approrimation, volume 17. Cambridge University Press.
14


Reviews:
[{"review_id": "u1kW9ZjrfX", "reviewer": "Reviewer_2SE6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. For these cascaded structures, the authors propose a novel algorithm by sequentially constructing the confidence region for the output of each layer and provide a theoretical guarantee for the performance.\n\n2. The author also provides a lower bound, suggesting that the upper bound is near-optimal.\n\n3. The paper is well-written and easy to follow.\n\n4. Experimental results also support the efficiency of the algorithm.\n\nWeakness:\n\n1. For bandit problems, most existing research focuses on scenarios with noise feedback (e.g., Sub-Gaussian noise), which are significantly more challenging than the noise-free case discussed in this work. In a noise-free environment, it appears that any agent could identify the optimal action by simply performing each action once. Therefore, it is crucial to provide an explanation of why a noise-free environment is relevant and important in the study of bandit problems.\n\n2. Regarding the lower bound, it is important to note the existence of an exponential dependency on $m$, represented as $O(c^m)$. In such scenarios, even a minor constant factor in $c$ can result in an exponential increase in the final regret. Hence, it is essential to specify the constant $c$ in the lower bound to facilitate a fair comparison with the upper bound.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work examines noise-free cascaded kernelized bandits across several different network structures, including chains, multi-output chains, and feed-forward networks. For these cascaded structures, the authors propose a novel algorithm by sequentially constructing the confidence region for the output of each layer and ultimately selecting the action with the highest upper confidence bound. They provide both upper and lower bounds for the regret in cascaded kernelized bandits and introduce a Non-Adaptive Sampling Based Method to calculate the confidence region. Additionally, experimental results support the efficiency of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weakness.", "broader_impact_concerns": "I do not find any potential negative societal impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2gRrvn7p6s", "reviewer": "Reviewer_Zmb1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n* This paper provides lower bounds for regret, which would be useful in subsequent studies.\n* The models and analyses discussed in the paper are clearly explained through figures and intuitive explanations.\n\nWeakness:\n* The regret upper bound of GPN-UCB includes a parameter $\\Sigma_T$ defined in Section 1.1, of which (non-trivial) upper bounds are still open.\n* It is doubtful that the way of citing the conjecture of (Vakili, 2022) is fair. (Please refer to \"Requested Changes\" for details.)\n* There is a lack of explanation of the motivation and application of considering noise-free (Although the motivation for setting up the cascade is explained).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers noise-free cascaded kernelized bandit problem in which all the exact intermediate results are observable. \nThe contribution of this paper includes:\n* An upper confidence bound-based algorithm, referred to as GPN-UCB, that achieves an upper bound on the cumulative regret. \n* A non-adaptive sampling based method that admits a simple-regret bound when the corresponding RKHS is associated with the Matern kernel.\n* An algorithm-independent lower bounds on the simple regret and cumulative regret.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have a concern about the way this paper refers to the conjecture of (Vakili, 2022).\nI would appreciate it if you could review the following concerns and either respond or correct the statements.\n\nIn this paper,\n$\\Sigma_T$ is defined as\n$$\n\\Sigma_T = \\max_{i \\in [m]} \\max_{z_1, \\ldots, z_T \\in \\mathcal{X}^{(i)}} \\sum_{t=1}^T \\sigma_{t-1}^{(i)} (z_t),\n$$\ni.e.,\nthis is defined as the **worst-case value** for the layer $i$ and the sample sequence $(z\\_t )\\_{t=1}^{T}$.\nOn the other hand,\n(Vakili, 2022) seems to conjecture that **there exists an algorithm** that achieves ideal regret bounds.\nIn particular,\n(Vakili, 2022) consider bounds on \n$$\n\\Theta_T^* = \\sum_{t=1}^{T} \\sigma_{t-1}(x_t^*)\n$$\nfor $( x_t^* )\\_{t=1}^{T}$ that is **chosen by UCB-type policies**\n(Some notation has been changed for consistency)\nas mentioned in Section 4.4. of (Vakili, 2022).\nIn fact,\n(Vakili, 2022) describes \n\"We however conjecture that the following regret bound is **achievable**\"\nand\n\"We conjecture that under certain mild regularity of the domain, \n$( x_t^* )\\_{t=1}^{T}$ are distributed nearly uniformly across the domain, in which case $\\sigma_{i-1}(x_i^*)=O(i^{-\\frac{\\nu}{d}})$\"\nwhich appears to impose some assumptions on $( x_t^* )\\_{t=1}^{T}$.\n\nFrom the above, there seems to be some gap between the \"conjecture of (Vakili, 2022)\" in the paper submitted to TMLR and the actual conjecture that (Vakili, 2022) had in mind.\nThus, it is questionable whether the original conjecture in (Vakili, 2022) implies the rightmost bounds in Table 1.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "niUur1g63d", "reviewer": "Reviewer_Sw3i", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and easy to follows. The results are satisfactory and provide improved regret bounds and new lower bounds.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of optimizing an m-layer function network in the noise free grey-box setting. The authors study different types of networks. They propose a new algorithm that improves the regret bound with respect to the state of the art. Moreover, they complement this result with nearly-matching lower bounds. Finally, the paper shows the empirical performance of the algorithm in simple experimental scenarios.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "None", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree the claims in the paper are backed by sufficient evidence and the results are sound. The paper provides lower bounds and algorithm guarantees and the proofs appear correct. Most of the reviewer concerns have been addressed in the author discussion, hence I believe the paper can be accepted as is.
Decision: Accept (poster)