Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms
Authors: Qian Yu
Yining Wang
Baihe Huang
Qi Lei
Jason D. Lee
Venue: NeurIPS 2023 poster (2023)
Keywords: optimization
quadratic bandits
sample complexity
optimality

Abstract: In stochastic zeroth-order optimization, a problem of practical relevance is understanding how to fully exploit the local geometry of the underlying objective function. We consider a fundamental setting in which the objective function is quadratic, and provide the first tight characterization of the optimal Hessian-dependent sample complexity. Our contribution is twofold. First, from an information-theoretic point of view, we prove tight lower bounds on Hessian-dependent complexities by introducing a concept called \emph{energy allocation}, which captures the interaction between the searching algorithm and the geometry of objective functions. A matching upper bound is obtained by solving the optimal energy spectrum. Then, algorithmically, we show the existence of a Hessian-independent algorithm that universally achieves the asymptotic optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions, which are enabled by a truncation method.

Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms
Qian Yu Princeton University gy4528@princet edu
Yining Wang University of Texas at Dallas
y yining wangeuttallas edu
Baihe Huang University of Califormia, Berkeley baihe__hunngbeekkeeyy edu edu
Qi Lei
Jason D. Lee
New York University ql 11518@nyu.edu
Princeton University
Jasond1@pzinnetoon.co
Abstract
In stochastic zeroth-order optimization, problem of practical relevance is under- standing how fully exploit the local geometry of the underlying objective function. We consider a fundamental setting in which the objective function is quadratic, and provide the first tight characterization of the optimal Hessian-dependee sample complexity. Our contribution is twofold. First, from an information-theereti point of view, prove tight lower bounds Hessian Hessian-dependent complexities by intro- ducing a concept called energy allocation, which captures the interaction between the searching algorithm and the geometry of objective functions. A matching upper bound is obtained by solving the optimal energy spectrum. Then, algorithmically, we show the existence of indeeeedenn algorithm that universally achieves the asymptotic optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions, which are enabled by truncation method.
Introduction
Stochastic optimization in the zeroth order (gradient-free) setting has attracted significant attention in recent decades. naturally arises various applications such as autonomous driving (12), AI gaming (22), robotics [14], healthcare (23), and education [13]. This setting is particularly important when the gradient of the objective function cannot be directly evaluated or is expensive.
An important case of interest in the zeroth order setting is the bandit optimization of smooth and strongly-convex functions. Although there are ample results regarding the minimax rates of this problem [1] g
6 3 24), little is known about how its complexity depends on the geometry of the objective function f near the global optimum x², as specified by the quadratic approximation (x x²"" 22 fx=" (xr x²). As initial step, investigate the following natural questions:
21
For zeorth-order bandit optimization problems of quadratic functions of the form } (a To)T A(x - zo), what the optimal instance-dependen upper bound with respect to A?
Is there an algorithm that universally achieves the optimal instance-dependent bounds for all quadratic functions, but without the knowledge of Hessian?
As our main contributions, we fully addressed the above questions as follows. First, we established the tight Hessian upper and lower bounds of the simple regret. Our bounds indicate asymptotic sample complexity bounds of Tr² (A-1)/ / (2c) to achieve accuracy. This covers the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

minimax lower bound of (e) in (21] Second, we prove the existence of a Hessian Hessian independent
algorithm with a matching upper bound of O (AT((A)))))) /ee). Thus, we complete the theory of zeroth-order bandit optimization on quadratic functions.
Related works beyond linear or convex bandit optimization. Compared to their linear/convex counterparts, much less is known for finding optimal bandit under nonlincar/non
reward function. A natural next step beyond linear bandits is to look at quadratic reward functions, as studied in this paper and some prior work (see reference bandit PCA
[15 4 its rank-1 special cases
18 11, bilinear
[0]. low-rank linear [19] and some other settings
5 (6]).
When getting beyond quadratic losses, prior work non-convex settings mainly focuses finding achieving e-stationary points instead of e-optimal reward [17), except for certain specific settings
(see, g.g..
7 25 26
20
26 20
2 Problem Formulation and Main Results
We first present a rigorous formulation for the stochastic zeroth-order optimization problem studied in this paper. Given a fixed dimension parameter d, let f B - IR be an unknown objective function defined on the closed unit Lz-ball B of the Euclidean space Rá, which takes the following form for some positive-semidefinie (PSD) matrix A.
f(x) (x zn) A(x zo).
For each time E [7]] an optimization algorithm A produces query point a; E B, and receives Yr f(x;,) w/:-
The algorithm can be adaptive, so that A is described by sequence of conditional distributions for choosing each 2; based on all prior observations {ær, Ur rree- Then we only assume that the noises {wr]r-] are independent random variables with zero mean and unit variance, i.c., E[w, æe. = 0 and E[wi [. 1.
For brevity, we use F(A) denote all functions satisfying equation (I for some zy B. We are interested in the following minimax simple regret for any PSD matrix A.
R(T; A) = inf sup E [f(xr]] SEF(A)
The above quantity characterizes the simple regrets achievable by algorithms with perfect Hessian information. We also aim to identify the existence of algorithms that universally achieves the minimax regret for all A, without having access to that knowledge.
Our first result provides tight characterization for the asymptotics of the minimax regret. Theorem 2.1. For any PSD matrix A, we have
lim sup RT: A) -) (Tr(A)t)**
T-
where A denotes the pseudo inverse of A3, Moreover, the distributions of we are i.i.d. standard Gaussian, the above bound provides a light characterization, i.e., there is matching lower bound that the following equality is implied.
lim R(T:A)- - (Tr(A-t))² T
We prove Theorem 2.1 in Section More generally, we also provide a full characterization of R(T: A) for the non-asymptotic regume, stated as follows and proved in Appendix C Theorem 2.2. For any PSD matrix A and T > 3 dimA, where dimA denotes the rank of A, we have
+
+ AR++1
if dimA
R(T; A)
(T<(A }1}² T
otherwise

---

where X3 is the jth smallest eigenvalue of A and K- is the largest integer in {0, 1, dimA} satisfying (Ek=>>
T 2 Ek-n
Xx² X5=
Remark 2.3. While our formulation requires the algorithm to return estimates from the bounded domain, i.e,, aT E B, our lower bound applies to algorithms without this constraint as well. This can be proved by showing that the worst-case simple regret over all f E F(A) is always achievable by estimators satisfying ar E B. Their construction can be obtained using the projection step in Algorithm and proof details can be found in Appendix
Finally, we provide a positive answer to the existence of universally optimal algorithms, stated in the following Theorem. We present the algorithm and prove its achievability guarantee in Section A
Theorem 2.4. There exists algorithm A, which does not depend on the Hessian parameter A, such that for A being any PSD matrix, the achieved minimax simple regret satisfies
lim sup E[f(xr) T T- = ((T((A ()( T-00 FEF(A)
Proof of Theorem 2.1
To motivate the main construction ideas, start by proving weaker version of the lower bound in Theorem 2.1 We use the provided intuition to construct a matching upper bound. Then we complete the proof by strengthening the lower bound through Bayes analysis and the uncertainty principle.
3.1 Proof Weakened Lower Bound
Assuming A being positive definite, we prove the following inequality when the additive noises wy 's are i.i.d. standard Gaussian.
lim inl R(T; A) T Ω (((T((A-)))))
(5)
T-x00
Throughout this section, we fix any basis such that = diag(A da). We construct a class of hard instances by letting
To E X2 a
(2,, xta) I6
+1
vk [d]
2T
We investigate Bayes setting where the objective function is defined by equation ①1 and my is uniformly random on the above set. For convenience, let a; = (I "ot,tt.....aa Fd,+) be the action of the algorithm at time f. We define the energy spectrum to be vector R = (R1--.g R&)) with each entry given by
R3 E
Intuitively, our proof is to show that an allocation of at least R₁ 2 2(A52x=5) energy is required to correctly estimate each 2a with 6(1) probability. Note that for any entry that is incorrectly estimated, a penalty of ((Ax=?) is applied to the simple regret. This penalty is proportional to the required energy, which is due the design of each zą- Meanwhile, the total expected energy is upper bounded by T', which is no greater than the summation of the individual requirements. Therefore, an ((1)) fraction of the penalty guaranteed, resulting in an overall effect of Ω (Es \x= Q (TT(A- on the simple regret.
Rigorously, consider any fixed algorithm, we define the estimation cost of each entry as follows.
E = E
da (IEET mx
3

---

For brevity, let (1g) The above function is minimized by the minimum mean square error (MMSE) estimator (e.g., see Sec. 4.6)). which depends on the following log-liielihod ratio (L.RR function.
SE 21 Vr 1r(T]
L - log
[[3 2 }r<T]
Specifically, the MMSE estimator is given by Tx.T - | Lanh Lg, and the resulting error condi- tioned on any fixed {ær, Vr Jr<T has an expectation of x sech Lr. lower bound for each cost entry.
Hence, we have the following
2
Es
2 AT - xxx²
Aa
sech² 2 Li
(6)
2
By the Gaussian noise assumption, the conditional expectation of LLR be written follows.
(ye- A xx)²)²
(yt
A + x²)
E [k E
$k
2sk (2 2
Σ
2
The above quantity equals the KL divergence between the distributions action-reward sequences generated by = =1. Clearly, it has the following connection to the energy spectrum.
E sk] = (A ? E
Σ
T = 2 (AuTR)) RR.
(7)
Recall inequality
(6). it also implies the following lower bound of the mean squared error.
La E [T&S8]] = E [ [st]]T)] [x]]] E T.,tanh
sech 2 La
4Eg
> 2 2F
> 2
(8)
Combine inequality and 8 the overall simple regret can be bounded follows.
[[((xr)] = Σ E Σ R Ag
(9)
k
Note that the definition of X' implies that the value of each xt is fixed. Hence,
(Σ, (Σ
) (Tr(A-t))
[f((xr) 2
Σ R
4T
8T
8T
8T
where the last inequality uses the fact that the total energy is upper bounded by the number of samples.
Finally, when T is sufficiently large, we have ||æo||2 < 1 almost surely, which implies that our instanen functions belong to the set of objective functions F(A). Therefore, E [f(xT)) provides lower bound of the asymptotic minimax regret, and conclude that
lim inf R(T; T (T<A-+t)² T-500
The validity of the hard-instaree functions requires T = =n (LEx Zx which is consistent with the transition threshold in Theorem 2.2 to the non con-asymptotic regimes.
3))
Remark 3.1.
3.2 Proof of the Upper Bound
Now we provide a proof for equation 4 which is implied by the following result. Proposition 3.2. For any PSD matrix A, let ke be the rank, >ı....,>k- be the non-zero eigenvalues, and E1, E2, .... C be the associated orthonormal eigenvectors. Then the expected simple regret achieved by algorithm Sacrrtthmmmaanne satisfies
1 (MAA-
lim sup E[f(xr)] T T-+00 JEF(A)
(10)

---

Algorithm 1 Hessian Dependent Algorithm
procedure HESSIAN DEPENDENT ESTIMATION(AI, A,,,.., A El,..., Ex., 7)
for k 1 too 1-t do
Let Rg 2,
(T 2d - 1), 4 = =RRx/2]-
Σ
Let og
(Sample(ex: 1x) Sample(-ess 1k)) Obtain an unbounded estimator
2
end for return øt BBB Ek AR (oos- x ex
D Projection to B
end procedure
procedure SAMPLE(Z, t) return the average of samples of f at end procedure
Proof. Consider an eigenbasis of A with Et, Eg- being the first k" vectors. For each k E [k*], the algorithm allocates R2 energy estimate the kth entry of Bog The value of Rg is chosen such that the hard instances in the earlier subsection maximizes (modulo a constant factor) the lower bound in inequality (9) (i.e., R3 satisfies of Rx( while ensuring the total number of samples does not exceed T - 1. By the zero-mean and unit-variance assumptions of the noise distribution, we have
E[(ax To ex)
2
T
2d
This essentially provides an unbounded estimator a 2
kk= Cgec that satisfies
k* AcE 20 2x) T
limsup sup E[[(@)
limsup sup T+000 #bEB
T fEF(A)
2
k=1
Σ j= X,
T
limm sup T+
2
T 2d
= TT( (T<(A-1))
(11)
Then, to obtain øy within the bounded constraint set, ã is projected to B under a pseudometric defined by matrix A. Due to the convexity of set B, we have f()) 2 f(xT) with probability (see Appendix A for proof). Therefore, incquality (O is implied by inequality (II).
3.3 Proof of the Lower Bound with Tight Constant Factors
To complete the proof of Theorem 2.1 it remains show that for standard Gaussian noise, we have
lim inf R(T; - (T<A-)t)²
(12)
T-xx
Notice that the object function and reward feedbacks depend only on the projections au and query points onto the column (or row) space of A. Hence, it suffices focus algorithms with actions that are constrained on this subspace. This reduces the original problem to an equivalent instance that defined on a (possibly) lower dimensional space and by a non-singular A. Therefore, only need to prove inequality 12 for those reduced cases (i.e., when A is full-rank).
We lower bound the minimax regret by comparing them with Bayes estimation error, where has a prior distribution that violates the bounded- norme constraint. Formally, for any fixed algorithm A, we consider its expected simple regret [[f())) over extended class of objective functions where f is defined by equation 4 but By is chosen from the entire Euclidian space. Then for any distribution of Zu, the overall expectation is upper bounded by the following inequality.
Fgg [E[[(x])]] < P(mo E B) sup [[[((T)) + E 1 & B) sup f(x) FEF(A)
(13)
aEB
5

---

where the first term on the RHS above is obtained by taking the supremum over all objective functions that satisfies 26 B, then the second term is obtained from the adversarial choice over all estimators for æo $ B. Compare the RHS of inequality (T3) with equation 3 lower bound of the minimax simple regret RT; A) can obtained by taking the infimum over algorithm on both sides. Hence,
it remains to characterize the optimal Bayes estimation error on the LHS.
To provide concrete analysis, let æo be Gaussian vector with zero mean and a covariance of T 3 Id- where Ia denotes the identity matrix Under this setting, conditioned on any realization of queries T1..... - and feedbacks y/...., -r- 1. the posterior distribution of Eo is proportional to
12 T
T-1 1 (y ( wo) A(æx, 20))
exp
2
Clearly, the Bayesian eтror can be lower bounded by the expectation of the conditional covariance, which is further characterized by the following principle (see Appendix [ for proof).
Proposition 3.3 (Uncertainty Principle). Let Z be random variable on any measurable space and 0 be real-vall valued random variable dependent of Z. If the conditional distribution of 0 given Z has density function fz (0), and In fz (0) has second derivative that is integrable over fz, then
1
[Var Z
8 202
In fz (0)
Hence, by taking the second derivative, the squared estimation enror for the kth entry of wo is lower bounded by the inverse the following expectation.
E
T
+
Σ
A(x, xo) σ0) TAT AT-
Aww
T
+
Σ
A(z: xo) =T0
ksk-
where (:)sk denotes the kth diagonal entry of the given matrix. Recall that we chose basis where A is diagonal. The overall Bayes error is bounded as follows
T Σ
1)
Fan [E (f(ar))] 2 Σ
7
A
(a., mo)
kkJ
where A (A)RE is the kth eigenvalue of A. By Cauchy's inequality, the RHS above can be further bounded by
Ex k x ))
(T(AAb))
Σx x5 + E
[ (EE ( (x:, - 2u)(II - xm)7)
kk 1)
T + TT-1 E
[ Zn 2ull
Note that by triangle inequality
[| 2011
SE <E (|
< (1+E || [1 [|]ool[]+]]== = -11+
s
where d is the dimension of the action space. We have obtained a lower bound of Eno [E (xT))] that is independent of the algorithm. Formally,
En [f(((r))]] 2 (Tr(A-t)) (T + +
A
We apply the above estimate to inequality
13
By taking the infimum over all algorithms,
inf Eze [[[((xr)
[1(20 & B) suppaes f(x)]
lim inf ((T TZ lim inf 7-400
7-400
P| E B]
For the purpose of our proof, the covariance of æa can be arbitrary long their inverse is asymptotically large but sublinear w.r.t. T'.

---

Observe that for our Gaussian prior,
lim Plao E [)] = 1, T-+00
lim E 1(2 $ B) sup f(z) 7-000
-T=0 O.
aEB
Hence, all terms above can be replace by closed-form functions. and we have
lim inf R(T;;A) T 2
lim inf inf Exo [[[f(xT]]] T T-000 A (MAA-))) / + + +
T-000
1
lim inf T-x
1 (T((A 2
4 Proof of Theorem 2.4
To prove the universal achievability result, we need to develop new algorithm to learn and incorporate the needed Hessian information. Particularly, the procedure required for achieving the optimal rates beyond simply adding initial stage with an arbitrary Hessian estimator, for there are two challenges. First, any Hessian estimation algorithm would result in a mean squared error of (1(1TT) the worst case, which translates to cost of ((1/TT) in the minimax simple regret. This induced cost often
introduces a multiplicative factor that is order-wise larger than the desired O ((Tr(A-b)) Second, to utilize any estimated Hessian, the analysis for the subsequent stages often requires the estimation error to have light-tail distribution, which is not guaranteed for general linear estimators when the additive noise in the observation model has heavy-tail distribution.
To overcome these challenges, we present two main algorithmic building blocks in the following subsections. The first uses oT') samples obtain rough estimate of the Hessian, and achieves low-error guarantees with high probability through the introduction of truncation method. The second estimates the global minimum with carefully designed sample points to minimize the error contributed from the Hessian estimation. We show that this sample phase can be written in the form of two-step descent. Finally, we show the combination of two stages provides an algorithm that proves Theorem 2.4
4.1 Initial Hessian Estimate and Truncation Method
Consider any sufficiently large T, first use To [T0.8] samples find rough estimate of A. Particularly, we rely on the following result.
Proposition 4.1. For any fixed dimension there is an algorithm that samples on To predetermined points and returns an estimation A, such that for any fixed a (0,0.5), 3 (0,+ and PSD matrix A,
lim sup P PIIĀ AlIF 2 To To JEFA
Toe 0,
(14)
where || denotes the Frobenius norm.
Proof. We first consider the ID case. Let y/+ V- and y each be samples of -1, and respectively. When the additive noises are subgaussian, we have that (y+ + yー - 2y) is an unbiased estimator of A with error that is subgaussian. By repeating and averaging over this process [To/3] times, the squared estimation eтror is reduced to O(1/To), and the normalized error is subgaussian, which satisfies the statement in the proposition.
However, recall that in Section 2 we did not assume the subgaussianity of wy. A modification of
the above estimator is required to achieve the same guanrantee in equation (14) Here propose a truncation method, which projects each measurement (y+ + y- 2y) to a bounded interval
[-T0.5 TO.5] Specifically, the returned Â is the average of [To/3] samples of max moixmmnn + y- - 2y, T -T0-5) which provides guaranteed superpolynomial tail bound. A more detailed discussion and analysis for the truncation method is provided in Appendix D.I
7

---

For general d, one can return an estimator that satisfies the same light-tail tail requirement, for example, by applying the above ID estimator repetitively poly(d) times to obtain estimates of all entries of A. Then the overall eroor probability is controlled by the union bound.
4.2 Two-Step Descent Stage
Let A be any estimator that satisfies the condition in Proposition 4.1 for = 0.4 and 3 = 1.6. Asymptotically, this implies the eigenvalues and eigenvectors of Á are close to that of A. We choose eigenbasis of Å and remove vectors with vanishingly small eigenvalues approximate the row space of A. Then, we estimate the entries of vo in these remaining directions following an energy allocation defined based on A.
Specifically, consider any fixed realization of Å, let X1, A2, ... be its eigenvalues in the non-increasing order, E2...... be the corresponding cigenvectors, and k' be the largest integer such that Aς- Z T-0.2. We present the detailed steps in Algorithm 2 where T₁ denotes the remaining available samples, i.e., T To-
Algorithm 2
procedure QUADRATIC SEARCH(A,, S2,,.., P Ci,..., Cx+, Ti) for + 1 to 1:" do
X
Let Pk
t [pk (Ti 4d 1)7.
1 1 jul
Let a
Truncated Diff @xy, 2k2 tx).
2d
end for
Let 5 = Ek CxCx, & = E min {1, |
Projecting to a O-centered hyperball
for k 4- to k-t do
Let 3x
Truncated Diff G 2. 1x).
Obtain an unbounded estimator
end for return Ør = argmin D GLēLEB Ex=1 de (3x. 0x)²
b Projection to
end procedure
procedure TRUNCATED DIFF(# æ1.()
for : 1 to do
Let y-. yー be sample of f at Zy. respectively
Compute the projection the difference y+ y- the interval [-t0.5 t0.3, i.c. let
= maxx(min(( end for
10.5 -10.5)
return "EE
end procedure
We the eigenbasis of À and let Ad be the diagonal matrix given by diag(Aj, Te .... dg- O, .... 0). In the first for-loop, we essentially estimated Arg, and then computed the first ke entries of its product with the pseudo-inverse of Ao (note that the rest of the entries are all zero). Since Åg is it to compute the optimal energy spectrum similar
good estimate of A with high probability, to the instance-dependent case, and allocate the measurements accordingly.
Recall the proof in Section 3 By the analysis of the truncation method in Appendix D.I the variable could have served as an estimator of xo if Ao A. where the estimation process reduces the Hessian-dependdnt case. However, Åo relies only on O(T0.8) samples, which generally leads to an expected penalty of (0.- w1177) in simple regret if used in place of A. We reserve fraction of samples for second for- to fine-tune the estimation in order to achieve the optimal Hessian-dependent simple regrets.

---

4.3 Regret Analysis
Recall our assumption on the Hessain Estimator and To = O(T0.8). The probability for 1| AllF 2 7-0.32 is (1/T).. As our algorithm always returns ær with bounded norms, the simple regret contributed by this exceptional case is negligible. Hence, we can focus on instances where ||A A T
Under such scenario, any non-zero A is close to a non-zero eigenvalue of A. Specifically, we have [ - Axl < 7-0.32 for all k, where each 0 the kth largest eigenvalue of A. Recall the definition of Ag- It implies that for sufficiently large T, k* equals the rank of A, and all non-zero eigenvalues of Ao are bounded away from zero. Consequently, ||4, I|e = ||A=1 + o(1)), which does not scale w.r.t. T. where M-1 denotes the pseudo-inverss for any symmetric M. We also have (Tr(A) ))2 O (T))))
The closeness between À and A also implies information on the cigenvectors of Åg. Recall that Ag is obtained by removing the diagonal entries of Á (in their eigenbasis) that are below a threshold 0-2 For sufficiently large T, the removed entries are associated with the d k- smallest eigenvalues, which are no greater than - Hence, as a rough estimate, we have ||Ao - A||: = o(T-..3).
These conditions can be used to characterize the distribution of æ. As mentioned earlier, from the analysis of the truncation method, each og concentrates around Ap AAo. Hence, concentrates near A/ AAzo, and the truncation method ensures that
[ -
Ao a Āo (aaAmo)] 0 ((TM(A ())))))))//==->> ( /T, (15)
PP
Ao
Azo
2 20 o (1/T).
(16)
Note that the norm of A, 'Ax is no greater than + o(1) under the condition of || Al|F o(3--.3). Formally, by triangle inequality
T Amolle S 11 Agæoll2 + ||ā,'(A - A)moll2 S + +11 'le -1 - AlL: = o(1)
We can apply inequality (16) to show that the Ln-norm of ã no greater than + o(1) with 1 - o(1/T) probability. Under such high probability cases, the projection of ã to the hyperball of
radius 1.5 remains identical. Hence, by the PSD) property of Ag. which is due to the convergence of its eigenvalues, we can replace all z in inequality (15) with and obtain that
E
[( c A
Au
A - ((TA /T.
(17)
The same analysis can also be performed for each Se, which concentrates near ēμ Ag A(2x0 - 3). Formally, let Te A Ee BRCR. we have
[ @T Ao A(2x0 - 3))² Ao TT A - m)] - /T. (18)
E
The above results for the two descent steps can be combined, using triangle inequality and Proposition below, to obtain the following inequality (See Appendix Dor their proofs).
E (कt - 2)T An (ØT =)] = O ((T((A)))))) IT.
(19)
(2A7' A (Ā.' Dy for brevity.
where we denote z $
Proposition 4.2. Let Åo, 7,y be variables dependent on a parameter T E IN, where Ao, 2 are PSD matrices and y belongs to the column space of Ag. If sims- || I1e < and limy- Āull: 0, then
Zy S (1+ 11Z - A (2 " Aoy) (1 + oz)) Aoy).

---

Assume the correctness of inequality (9), the remainder of the proof consists of two parts. First, we show that the vector 2 can be viewed Taylor approximation for projection of zo onto the column space of Ag. hence, ëт could achieve the needed simple regret. Then, we show that the projection of Ty the unit hypersphere to obtain Zy induces negligible cost, that the validity constraint can be satisfied the same time.
For the first part, let P1 denote the projective map onto the column space of Ag, i.e., Pi A (here and in the following, A denotes the pseudo inverse of Ag). We consider the Hessian of on this restricted subspace. which is given by A - PIAP Note that the definition of Ao implies Ao Pj P. We have || - ALlII = ([ - Pi |F - || - All: - T-3.32 Then recall that the non-zero eigenvalues of Ao are bounded away from 0, i.e., || A o(T0.32). We have that A invertible within the column space of Ao (i.e., A AI P1) for sufficiently large T.
The pseudo inversion of A provides point of equivalence to 2 within the column space of Åg- Particularly, let 2u _ AT I Axz. we have Piz z z and f(x) = (a 1ec-za) A zu) for any x E Rd and sufficiently large T. The second equality is due to A(zo z0) (A AA, a)) 0 for sufficiently large T, which is implied by the following proposition (see Appendix D.4 forffor a proof).
Proposition 4.3. For any symmetric matrix A and any symmetric projection map P1 (i.e., P? P1
PT) if A & PLAP and A has the same rank, then the pseudo inverse A satisfies A = AAi" A.
We show that the error = - Zu is bounded by o(T5). Observe that PT = Ap P1 = Ag and AT P1 = AT'. we have
2 2A A - (Ao ((6'A))) 2 x0 = A ((20- - AT=1) - Ax
20 (AT'A A
From 11 AIllE S T..332
||ā ||F =1AĀ~1|1 0() and the fact that A is restricted to the (l(0))))-O((,,,,,. which also does not scale w.r.t.
column space of Åg. we can derive that
T. Therefore, the above equality implies that ||2 zoll2 o(T--..). As consequence, we have
following inequalities due to inequality [9) and triangle incquality.
E ( =0)" Ao (ăT 20)] = ((T((A IT,
(20)
For the second part, we first note that the 1.2 norm of zo is bounded by the spectrum norm of AT A. Specifically,
Amolla S || = AlAl'A
||0|||2 12 ||4T All S ||AT*A||,
where || || denotes the spectrum norm. Recall the definition of AI, we have AAA
AT 1 A1 AT A1 Hence,
||4T* A|I = || AT A2 1T || = 47 (A1 + (A A1)) A = P1 + ' (4 A1)² AT
< P1 || + 4 - 2 AT
(A-A1)
Note that ||4 - A.IFF |
A AIIFF + A1Ao AIlF= < 0.3.. By the fact that ||AT ||F
||Ā-~I|e-- (L)), we have || AlI2 < 11
and |zoll2 1|/222100 S 1 + o(T-00.).
Therefore, we have min (zo- x))AA(22 - x) o The projection of कर to the unit hypersphere guarantees the following bound (see Appendix A for proof).
(ΦT - - Ao (IT =o)] E (कT
20)_ Ao (ØT zo) + 1(T = O ((TT(A ST.
Note that both øy and 2o belong to the column space of Ao. From Proposition 4.2 Ao by A for the above inequality and obtain
can substitute
E [( =0) A (WT =0)] = O ((TT(A- /T.
(21)
Then the theorem is proved from the fact that f(xT) (ØT =0) A(xT 200.
10

---

References
[1] A. Agarwal, O. Dekel, and L. Xiao, Optimal algorithms for online convex optimization with multi-point bandit feedback. In Colt, pages 28-40. Citeseer, 2010.
[2] D. Bertsekas and J. N. Tsitsiklis. Introduction to probability vol. 2002.
[3] S. Bubeck, Y. T. Lee, and R. Eldan. Kernel-based methods for bandit convex optimization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages
72 85, 2017.
[4] D. Garber, E. Hazan, and T. Ma. Online learning of eigenvectors. In International Conference on Machine Learning, pages 560-568. PMLR, 2015.
[5] A. Gopalan, O.-A. Maillard, and M. Zaki. Low-rank bandits with latent mixtures. arXiv preprint urXiv: 0150, 2016.
[6] E. Hazan and K. Y. Levy. Bandit convex optimization: Towards tight bounds. In MIPS, 2014,
[7] B. Huang, K. Huang, S. M. Kakade, J. D. Lee, Q. Lei, R. Wang, and J. Yang. Optimal gradient- based algorithms for non-concave bandit optimization. arXiv preprint arXiv:2107.044 00000,0..88,,,.. 2021.
[8] K. G. Jamieson, R. Nowak, and B. Recht. Query complexity of derivative-free optimization. Advances in Neural Information Processing Systems (NeurIPS), 2012.
[9] N. Johnson, Sivakumar, and Banerjee. Structured stochastic linear bandits. arXiv preprint arXiv: 160ivv1606.000 05693, 2016.
[10] K.-S. Jun, R. Willett, S. Wright, and R. Nowak. Bilinear bandits with low-rank structure. In International Conference Machine Learning, pages 3163-33 1172. PMLR, 2019.
[11] S. Katariya, B. Kveton, C. Szepesvari, C. Vernade, and Z. Wen. Stochastic rank-1 bandits. In Artificial Intelligence and Statistics, pages 392 401, PMLR, 2017.
[12] B. Kiran, Sobh, V. Talpaert, Mannion, A. A. A. Sallab, S. Yogamani, and P. Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent
Transportation Systems, 23(6):4909-4926, 2022.
[13] R. F. Kizilcec, J. Reich, M. Yeomans, C. Dann, E. Brunskill, G. Lopez, S. Turkay, J. J. Williams, and D. Tingley. Scaling up behavioral science interventions in online education. Proceedings of the National Academy of Sciences, 1 117(26): (006)):1990014400
2020.
[14] J. Kober, A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey. Springer Tructs in Advanced Robotics, 97:9-67, 2014.
[15] W. Kotlowski and G. Neu. Bandit principal component analysis. In Conference On Learning Theory, pages 1994-2024. PMLR, 2019.
[16] S. Lale, K. Azizzadenesheli, A. Anandkumar, and B. Hassibi. Stochastic linear bandits with hidden low rank structure. arXiv preprint arXiv:1901.09490. 2019.
[17] J. Larson, M. Menickelly, and S. M. Wild. Derivative-fres optimization methods. Acta Numerica, 28:287-404, 2019.
[18] Lattimore and B. Hao. Bandit phase retrieval. arXiv preprint arXiv:2106.01660 2021.
[19] Lu, A. Meisami, and A. Tewari. Low-rank generalized linear bandit problems. In International Conference on Artificial Intelligence and Statistics, pages 460-468. PMLR, 2021.
[20] E. Moulines and Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
[21] O. Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. In Conference Learning Theorr, pages 3-24. PMLR, 2013.
[22] S. Yildirim and S. B. Stene. A survey the need and use of Al in game agents. InTech, 2010.
[23] C. Yu, J. Liu, and S. Nemati. Reinforcement learning in healthcare: A survey. In arXiv preprint arXiv::908.000 08796, 2020.
[24] X. Yu, I. King, M. R. Lyu, and T. Yang. A generic approach for accelerating stochastic zeroth-order convex optimization. IJCAI, 2018.
[25] I.. Zhang, T. Yang, R. Jin, and Z.-H. Zhou. Online bandit learning for a special class of non-convex losses. In Tietty-Ninth AAAI Conference Artificial Intelligence, 2015.
11

---

[26] P. Zhao and L. Lai. Optimal stochastic nonconvex optimization with bandit feedback. arXiv preprint 17X::22103.16082, 2021.
12

---

A Projection Lemma
Proposition A.1. For any PSD matrix A with dimension d, any closed convex set B in the Euclidian space R and R let
x² argmin g g x)
#EB
where
g(u, v)) - (u - TTTAAA v),
then
g( 20) S gg
VwD B.
More generally,
g(x" z0) S g(0
+ -min ((0. x)
Vzn E Rd.
=EB
Proof. We first provide a proof for wo E B. For any a E [0, 1]. let
La ax" + (1 - a)
By convexity, we have Ia for any a. Note that g x.) is differentiable. By the definition of x²" we have
1 8
(x" (Z)-=) - -xn)
g (1, x.)) a==1
5 0.
2 da
Therefore,
g(x" a0) = -g( x0)) + 2(x A 20) ggxx((" S g(0, 20).
where the last inequality uses the PSD property of A.
Now we consider the more general case and let æ be any vector in B. Following the same steps in the earlier case, we have
(x* -TT x) s
Hence,
x(x",20) gg 20) = 2(x" A(x" 20) - g(x", (x",a) 3)
T)T A(x 20) g( ,,'))) .) < 2(x'
0(20, x)
(ær 20 x² + T) A (x.
x= .)
S g x).
Note that the above inequality holds for any a E B. The proposition is proved by taking the minimum over æ.
B Proof of Proposition 3.3
Proof. We first prove for the case where Z is deterministic. Let denote the conditional expectation of 0. By Cauchy's 's inequality,
E[(0 1z) E =(00 In (2
θ In fz (0)
z 2 (0 (0-z))
2
(22)
00
13

---

The quantity on the RHS above can be bounded as follows.
(0- =100
0 = / (0- uz)
E
pz)
00 fz
fz (0)
fz(O)do
00
/
(0 pz)
fz (0)
d0
00
T
0
lim sup
(0 pz)
fz (0)
T++*
-
00
lim
((0 - uz pz) fz (0)lzz()
8=1 p--))= PPO [-T,T]]
7+++00
2 1,
where the last inequality the integrability of fz, which implies
lim (0 uz)zzzzzzzzzzz)zz (0) -- -
8=T
T-++00
Then we evaluate the second factor on the LHS of inequality integrable, the following limit exists.
22
Recall that
8² 207
In fz( is
82
0² 002
E
In fzz (0)
Z = lim
fz (0)
In fz (0)
002
T-++00
-T
Then by positivity, we also have
( 00
[
a
f2()
2
Z lim [ fz())
( In fz f2(0)) 2
E
d0.
30
we focus the non-trivial case where the first limit is not -o, the above two equation implies the existence of the following limit.
E
82
In fz
(0)
Z
+E
(
0
In (2()
Z
002
30
(
O2
0
In fz 200)) )
= lim
fz(0)
In fz (0) +
do
T
-T
002
00
0
0-T
= lim
f0)
In fz())
T
00
B==T
0
8=T
= lim
(z(
30 T-+
-=-
The result of the above equation has to be zero, because the limit points of 8 (0)) must contain zero on both ends of the real line, which is implied by the integrability of fz. Consequently, we have
[(
i In (2( 00
02
E
Z =
E
In fz( (0) Z
(23)
002
Then, the special case of Proposition When Z is variable, we simply have
3.3 with fixed is implied by incquality
22
(
a
In s2(0))
Var Z
>
I/E
a0
1
E
In fzz(zz(() (0)) 2
38
Then the proposition is implied by equation
23
14

---

C Proof of Theorem 2.2
We first investigate the lower bounds. Observe that the proof provided in Section 3.1 only fails when the constructed hard instances have ||00||2 1. Hence, have already covered the T >
(E-n x Ex=1 XT2 case, i.e., when h- dimA d. It remains to consider the other scenarios, where k* < is satisfied.
By the assumption that T (E (E (EE
one instead set the entries of ano in the earlier proof with indices greater than k to be zero, so that | S 1 is satisfied. Formally, let the hard-instance functions be constructed by the following set.
Zo E X4 & {
A
(21, .... TK ........ 0) 24= =
Ah [K^]
2T
Then by the identical proof steps, we have R(T;A) =s
Next, we show that R(T; A) (Ac+++)))) We assume the non-trivial case where Ag++1 # O. Note that RT; A) is non-increasing w.r.t. T. We can lower bound R(T; A) through the above steps but by replacing with any larger quantity. Specifically, recall that k* is largest integer satisfying T
Σ - A5
(Etn Ax )) which implies T
Σ k=
x +)
Ekit' Xx >..). We have,
1'+1 Σ
RT; 2 R
Notice that this change of sampling time allows to apply the earlier lower bound with k* incre- mented by 1.
$ 2
>
k=
R(T; A) 20
+1+1 +1
A
k==l Xxx
k=
+1
A
= 1(2xx+111
xx
To conclude,
1) ((2ii) x
k Ex
X
R(T: A) = Ω max
+ A
T
T
which completes the proof of the lower bounds.
The needed upper bounds can be obtained by only estimating the first k. entries ag-
Remark C.1. The requirement of > dimA the Theorem statement is simply due to the integer constraints for the achievability bounds. Indeed, when AdimA is large, it requires least Ω (dimA) samples to achieve O(1) expected simple regret.
D Proof Details for Theorem 2.4
D.1 Truncation Method and Its Applications
The truncation method is based on the following facts.
15

---

Proposition D.1. For any sequence of independent random variables X1, ..... Xn and any fixed parameter m satisfying m max; [[[X Let Z max(min Xx, m), -m] for any &s [n], we have
[[ZA]] E[Xx]] - 3 m [E[X,]]
Var[XR]
(24)
Var [x) SF F
(2x- -F(Xa)) xx]
(25)
Moreover, for any 2 > O, we have
1 Σ m
Var [
P
Σ x
ΣE[Xa]
E[X
22 S exx
(26)
[[
m
Proof. The first incquality is proved by expressing the LHS with piecewise linear functions. Note that by the definition of Zg. we have
[F - E[X+]] = |F [maxx ( (-m - XR, 0}] Fl [mmax { [x m, 0}]]
1 [/maax -m Xx, 0}]
|E[max Xx. 0Hl
= E [maax - m. 0}}.
We apply the following inequalities, which holds for any m 2 |E[X&]]-
1
X - E[xx11
Xx m S Xx - E[Xx] m E[XA]
S
4
E[XR]
Therefore,
XR 1
[[|Z - -EXx
S
4 m
E[XA]
1 Var [ar[X
4
m [[[Xa]]
The second inequality is due to the following elementary facts,
EI =[X,)))]<[((X, E[X+])*]
Var[X*], Var()))
where the inequality step is implied by the definition of Zn and the condition > max [E[Xa]]-
To prove the third inequality, we first investigate the following upper bound, which is due Markov's inequality.
Ele m CE 2x Ex F(X.)))
P
Σ k
Zx
E[Xx] 2 2
k
Ele d (Ze E(Xx))
(27)
The equality step above is by the fact that Z₁ 's are jointly independent. For each k, using the fact that Zy is bounded, particularly, Z E[Xx] I m + |E[Xx]] we have the following inequality
1 + (Zn-E(X)) - 1- (Zx E[Xx]) s (Z+- E[X+]) e (m+1E[Xx+D
(m + IE (xII)
m
(m + |
For brevity, let
|E[Xa]l
We combine the above bound with inequality (4 and (25) to obtain that
m
(2 = -1+E
1 Zn E(Xx])
+E e
(2xx))())))
1 - (Zx E(X,))
Var [Xx]
cl+0 -2
< 1 +
4 + (1 0)
(28)
m(m
[[(x&]])
(1+0)
16

---

Recall that 0 < 1 as assumed in the proposion. From elementary calculus, we have
Var
[X:]
Ele (2x
S 11+
m
[[[x
Var [ar
S exp
m(m
[E(Xx]])
Therefore, recall inequality 27 we have
Σ
Zx
Σ
[[X+] 2
S exp
Σ
Var [ar[X
m(m
[x]]]]
m
By symmetry, one can also prove the following bound through the same steps.
P Σ Z EE(xA]
- S exp Σ
Var Xx]
m(m - [[
m
Hence, the needed inequality is obtained by adding the two inequalities above.
Now equation [14) for the 1D case immediately implied by Proposition D.I of A the proof, for any sufficiently large To. we have
Recall the construction
T T..5-a
P A 2 < 2exp
3
3
T
Remark D.2. Instead of projecting to a bounded interval, the same achievability result can be obtained the average over any functions that map the samples [-T8. To.5] while imposing an additional error of o)) everywhere. This includes T)n uniform quantizers, which naturally appear in digital systems, over which exact computation can be performed to eliminate numerical errors. We present this simple generalization in the following corollary.
Corollary D.3. Consider the setting Proposition D.I
Let Yı,..., Yn be variables that satisfy
|Yx Zul < for all k with probability 1. We have
Σ Yk
F(X8] k
2 2
S 2exp
Σ
Var Var[Xg]
2 bn
m(m [E[Xx]])
m
D.2 Proof of Proposition 4.2
Proof.
7T T Aoy = (T Āoyy I 11 - Flll
1 $ 2 A T Aou).
D.3 Proof of inequality
19
We apply Proposition 4.2 to inequality
17 and let 7 AA,11 A. Note that
|| Āollr s 2
Ao |F + [I(A Ao) Ao)l o(1);
which satisfies the condition of Proposition 4.2
Using the fact that A, Ao = Aoo
we have
E
[ A A ( - Ao¹1 Amr)
An
( 1 A A ))]
@ Ao Awo)
T
Z
Au Auo) o ((Tr(A /T.
(29)
Then by the triangle inequality for the PSD matrix Åg. the combination of the above inequality and inequality (18) gives
E ( - 2) Ao (Ør - 2)] = 0 ((TT(A--)))) IT.
17

---

D.4 Proof of Propasition 4.3
Proof. When A₁ and has the same rank, the map P1 is invertible over the column space of A. Under such condition, there exists matrix X such that A X A. Note that A ATAT² Pt. We have X X P
AAT! Therefore, the needed A AAT A is obtained by multiplying on the right-hand sides in the above identity.
18


Reviews:
[{"review_id": "Yg6zE3bh3E", "reviewer": "Reviewer_tYpf", "summary": "This paper studies zero-th order quadratic optimization with bandit feedback. It provides a comprehensive analysis of the optimal sample complexity, which depends on the Hessian of the objective function. There are two contributions. Firstly, it establishes lower bounds on Hessian-dependent complexities using the concept of energy allocation, capturing the interaction between the search algorithm and the geometry of the problem. The matching upper bound is achieved through optimizing the energy spectrum. Secondly, an algorithm is presented that achieves asymptotically optimal sample complexities for all Hessian instances, independent of the Hessian. These optimal sample complexities remain valid even for heavy-tailed additive noise distributions, enabled by a truncation method.", "questions": "What is $dimA$? It is not defined. Is it just $d$?\n\nIn Line 67, in the definition of the effective dimension $k^*$, do you miss a fractional number notion? i.e., $/$ Otherwise, it would be an ill-defined dimension.\n\nThe construction of the lower bound is a bit strange. When you construct x_0 in this way, it will naturally lead to the definition of the effective dim $k^*$. I’m wondering if the current lower bound is truly essential, or just an artifact?\n\nIn my opinion, the non-asymptotic lower bound (Theorem 2.2) is more interesting, why don’t you present it instead of proving a weaker (and asymptotic) lower bound in the main paper?", "limitations": "The zero-th order quadratic optimization problem is a bit simple. But it is a good starting point\n\nThe lower bound proof technique lacks generality. It might be simplified by the generalized le cam’s method. See the textbook “Bandit algorithms”", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. If the result is correct, it provides matching upper and lower bounds for quadratic bandits, which is pretty nice\n\n2. The results hold even for heavy-tailed noise with the help of truncation.", "weaknesses": "1. The definition of the effective dimension $k^*$ does not look correct\n\n2. The proposed algorithm needs to know a lot of problem-related quantities, which is not practical\n\n3. There is no experimental evaluation", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments. We have now provided the following point-to-point response.\n\nQ1: The definition of dim$A$?\n\nA1: In the submitted version, our result is stated for dim$A=d$ where dim refers to the dimension of the Euclidian space over which A is defined. While our result holds true under this definition, it later came to our awareness that Theorem 2.2 still holds if dim$A$ instead denotes the rank of $A$, and the proof follows almost the same arguments. We plan to let dimA denote the rank of A in the revised version and update the proof steps accordingly.\n\nQ2: The definition of $k^*$ in line 67?\n\nA2:  We would like to verify that the condition of T in line 67 is correct under the convention of $0^{-1}=+\\infty$. So, $k^*$ is always no greater than the rank of $A$. As we plan to update the definition of dim$A$ to be the rank of $A$, this clarity issue is automatically resolved as $\\lambda_k^{-\\frac{1}{2}}$ for $k\\in\\{1,2,...,\\text{dim} A\\}$ is always finite.\n\nQ3: Is the current lower bound truly essential or just an artifact?\n\nA3: First, we would like to clarify that the provided bounds themselves are fundamental as they are matched by upper bounds, and the choice of $k^*$ only affects how the bounds are presented. The transition threshold of T in Theorem 2.2 (or the definition of $k^*$) is fundamental to some degree, as in certain regimes, this specific choice of $k^*$ is required for the bound to be order-wise tight. There could be potential flexibility in how $k^*$ is selected for certain cases, but we choose to present one concrete example in our theorem for brevity.\n\nQ4: Why prove a weaker (and asymptotic) result in the main paper instead of the non-asymptotic lower bound (Theorem 2.2).\n\nA4: First, we would like to clarify that Theorem 2.1 is not merely a strictly weaker version of Theorem 2.2 as it characterizes the exact constant factor for the minimax asymptotic regret. Besides, the main paper focus on the proof for the asymptotic case for the following reasons: 1. The proof of Theorem 2.1 contains all essential ingredients (Theorem 2.2 is proved following exactly the same construction ideas, but with additional technical details in the analysis); 2. the statement of the theorem 2.1 is simpler compared to the non-asymptotic case, so the readers are not lost in technical details; 3. Theorem 2.1 is essential for understanding the significance of Theorem 2.4.\n\nQ5: Comparison to le cam’s method.\n\nA5: We would like to thank the reviewer for pointing out the reference. Compared to classical methods, such as le cam’s method or general lower-bounding approaches for bandit algorithms, a key distinction in our proof is to construct hard instances and provide analysis tailored for each Hessian instance. To the best of our knowledge, our proof (especially the analysis in Section 3.3) may not be directly obtained from earlier approaches, and we believe our proposed techniques can be a stepping stone to be applied for more general settings.\n\n"}, {"review_id": "EBn2MPUd9q", "reviewer": "Reviewer_q1aQ", "summary": "The paper considers the black-box optimization problem of quadratic functions specified with PSD matrices. The paper shows matching upper and lower sample complexity bounds depending on the matrices. For the upper bound, the paper proposes algorithms.", "questions": "Do the proposed algorithm work for general convex functions?\n\n\nI read other reviews and rebuttal comments. The rebuttal answers my question sufficiently. But I would keep my score the same since my concern about the motivation is not resolved.", "limitations": "As raised above, the technical results are solid, but practical usefulness is limited.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper gives tight upper and lower sample complexity bounds for the black-box optimization of quadratic functions. The strength of the result is that the bounds depend on the PSD matrix, which means the bounds are instance-dependent. These results recovers previous results as well.", "weaknesses": "I feel that the focus of the paper is a bit narrow. So far, I do not know any motivating situation where we need to solve some black-box optimization of quadratic functions. Although the results are technically solid, their motivation and practical usefulness are not strong enough. \nThe paper would be better evaluated for more theory/optimization-oriented conferences/journals. \n\nOr, if the proposed algorithms were more practical, say, it works for general convex functions but works better when the function is quadratic (best-of-both-world type algorithms), I would evaluate the paper higher.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback. Convex quadratic functions depict the local geometry of strongly convex functions near the critical point, and their sample complexity remains an open question in the online learning community. Although our result does not directly apply to general convex functions. Fully characterizing the sample complexity in this important (quadratic) case can serve as a stepping stone that provides essential techniques and a better understanding of how to achieve optimal sample complexities in general cases."}, {"review_id": "LUaf3KM0QK", "reviewer": "Reviewer_Cwak", "summary": "This papers studies quadratic stochastic zeroth-order optimization and provide lower and upper bounds on the minimax simple regret. First, the authors provide an asymptotically tight upper bound of $\\frac{1}{2}({\\rm Tr}(A^{-1/2}))^2$ where $A$ is the Hessian of the quadratic. Then, the authors provide asymptotic lower bounds which take two distinct expressions depending on properties of $A$. Next, the authors show the existence of a universally optimal algorithm, meaning that it asymptotically achieves the Hessian-dependent bounds without accessing the Hessian information.", "questions": "- \"Energy allocation\" seems to be the same as \"energy spectrum\" defined in Section 3.1. Please formally define energy allocation or unify the terminology.\n- Line 207: serve --> served.\n- Line 195: remove \"an\".\n- Please formally define Truncated Diff (projecting the diff onto [-t, t]) and other simple operations in the algorithms (Simple Project, etc.).\n- Regarding Section 4.1, are there potential ways to do better than applying the 1D estimator poly(d) times to obtain an estimate for $A$? Are there more efficient join estimators that make use of $A$ being p.s.d.? If so, it would be helpful to point out (without incorporating them in this paper's analysis as it does not seem necessary). It might still be useful in future finite-sample analysis.", "limitations": "The authors defined the scope of this paper to be within specific problem setups. This work is largely theoretical and does not have potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Clear problem statement and result presentation.", "weaknesses": "See **Questions**.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments, and will revise the identified typos. Below are the point-to-point responses to the comments.\n\nQ1: Energy allocation vs energy spectrum\n\nA1: Energy spectrum refers to the particular function defined above line 86, and we used energy allocation to refer to the act of designing the algorithm to match the energy spectrum to any particular vector (e.g., assign $2t_k$ samples to the $k$th dimension in Algorithm 1). This will be better clarified in the revised version.\n\nQ2: Formal definition of subroutines\n\nA2: Thanks for the suggestion, we will add the formal definitions in the corresponding algorithm enviromennts. For example, we will revise the pseudo code of the truncated diff as follows:\n\n  - For $k\\leftarrow  1 $ to $t$\n\n    + Let $y_+$, $y_-$ each be a sample of $f$ at $x_0$, $x_1$, respectively\n    + Compute the projection of the difference $y_+-y_-$ to the interval $[-t^{0.5}, t^{0.5}]$, i.e., let $z_k=...$\n  - End for\n\n  - Return the average $\\frac{1}{t} \\sum_{k=1}^t z_k $\n\nQ3: Better ways to estimate the Hessian?\n\nA3: Instead of estimating the Hessian entrywise, there are several possible alternatives, e.g., see  the following paper [A]. However, for quadratic f, Hessian estimation entrywise is order-optimal (in terms of squared Frobenius norm of the error): As a lower bound, learning the hessian is harder than learning a vector length $d(d+1)/2$ by observing its unit projections under Gaussian noise (because sampling any $f=x^{\\intercal}Ax$ essentially returns a noisy version of a projection of its $n(n+1)/2$ independent entries), hence we need at least $\\Omega(d^4/\\epsilon^2)$ samples to achieve a squared estimation error of $\\epsilon^2$. This exactly matches the error achieve by entry-wise estimation. For the same reason, the PSD property will not reduce the optimal sample complexity beyond a constant factor.\n\n[A] Balasubramanian and Ghadimi, “Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points”\n\n\n"}, {"review_id": "c2kavI1K6z", "reviewer": "Reviewer_gm1W", "summary": "The paper considers the problem of Quadratic Hessian bandit and establishes both lower and upper bounds on algorithm performance to provide a characterization of simple regret in this setting. The authors also propose an algorithm that is agnostic to the knowledge of the Hessian.", "questions": "The choice of $x_k$ and the lower bound on $T$ in Theorem 2.2. (line 67) are rather interesting. Do you have an intuitive/physical explanation of why that particular expression comes up or what that represents? I haven't come across that combination of $\\lambda_k^{-3/2}$ and $\\lambda^{-1/2}$ anywhere else and it might have something fundamentally insightful.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper considers a new problem on quadratic bandits and provides a complete characterization of simple regret in the setting. The completeness and tightness of the results paints a clear picture of the results about this new problem.", "weaknesses": "One thing that the paper needs to improve upon is the writing. The exposition lacks a flow and proofs of the theorems seem to be all over the place.  Some points that I realized can be improved:\n1. The proof of Theorem 2.1 can be improved. It took me quite a bit of effort to understand the steps mainly because some intermediate steps were missing. The missing steps were non-trivial in the sense if they are missing, it is not easy for the reader to make the connection unless they have several results handy. I would suggest to please ensure that the proof is largely self-contained and it can be understood by the reader without actually having them to do intermediate steps. If it cannot be accommodated in the main text, you can move some intermediate result to Appendix or atleast provide a citation of some the results being used in the intermediate steps e.g. MMSE estimator. Also I think you are missing an \"$L_k$\" in equation 7.\n2. The statement of Theorem 2.1 is not clear. From the text leading upto it and the proof, it seems that it is a statement about the lower bound. But there is no lower bound anywhere in the statement of the theorem (apart from the one that is implicit in the limit for Gaussian noise). I would suggest to please make the statement of theorem clear and precise.\n3. Similarly, the way Theorem 2.4 is phrased, it is (almost) immediate from the current statement of Theorem 2.1. I think in addition to universal optimality you also need to mention that this algorithm does not need the prior information about the Hessian. This not only makes the theorem clearer but also stronger.\n\nIn addition to the above comments, I encourage the authors to please check the exposition for consistency and flow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the suggestions and below are the detailed responses.\n\nQ1: Details for the Proof of Theorem 2.1.\n\nA1: We will provide additional details for the intermediate steps, including additing a reference for the optimality of MMSE estimators. We will also correct the typo in equation (7).\n\nQ2: Clarity on the statement of Theorem 2.1.\n\nA2: We would first like to clarify that Theorem 2.1 contains both upper bounds and lower bounds, only that the proof of the upper bound is much simpler. We decided that the upper bound is to be included as it can be compared to Theorem 2.4. However, we can better emphasis the lower bound by revising the last sentence to be “..., i.e., a matching lower bound implies the following equality”.\n\nQ3: Clarity on the statement of Theorem 2.4.\n\nA3: Indeed, in Theorem 2.4 we are exactly providing an algorithm that is independent of the Hessian (which turns out to be non-trivial compared to its counterpart in Theorem 2.1). We will revise the statement to “There exists an algorithm $\\mathcal{A}$, which does not depend on the Hessian parameter $A$, such that for $A$ being any PSD matrix, the achieved minimax…” to better clarify this fact.\n\nQ4: Choice of $x_k$ and the transition threshold of $T$.\n\nA4: Intuitively $x_k$ is selected such that the sample complexity for learning the sign of $x_k$ is proportional to the penalty of an incorrectly estimation, so that the performance of an algorithm on these special cases is roughly independent of how many samples are used in each direction. The explicit exponents ($1/2$ and $3/2$) is a result of the quadratic growth of the objective fuction. We believe that if the function class is instead in the form of $f=\\sum \\lambda_k (x_k-x_{0,k})^{\\alpha}$ for some general $\\alpha$, then the correct $|x_k|$ for the hard instances will be proportional to $\\lambda_{k}^{-\\frac{3}{\\alpha+2}}$."}]

Author rebuttal:

Meta-review: This paper considers the problem of instance-dependent zeroth-order (bandit) convex optimization. Focusing on quadratic objectives, the main result of the paper is to provide algorithms that optimally adapt to the geometry of the problem instance under consideration via the Hessian, which they characterize via matching upper and lower bounds.

Reviewers agreed on the importance of developing an understanding of instance-dependent guarantees for zeroth-order optimization. They found the paper's algorithms and proof techniques to be novel, and agreed on the significance of characterizing the optimal hessian-dependent problem complexity. While some reviewers raised concerns around practicality and the restriction to quadratic objectives, they did not defend this position in discussion, and I believe it is appropriate to leave these issues for future research given the challenging nature of the problem.

For the final version of the paper, the authors are encouraged to incorporate the clarifications suggested by the reviewers.
Decision: Accept (poster)