Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity
Authors: Qian Yu
Yining Wang
Baihe Huang
Qi Lei
Jason D. Lee
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic Optimization
Sample Complexity
Optimality
Primary area: optimization

Abstract: Optimization of convex functions under stochastic zeroth-order feedback has been a major and challenging question in online learning. In this work, we consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. 
We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds. 
We propose an algorithm that features a combination of a bootstrapping stage and a mirror-descent stage. 
Our main technical innovation consists of a sharp characterization for the spherical-sampling gradient estimator under higher-order smoothness conditions, which allows the algorithm to optimally balance the bias-variance tradeoff, 
and a new iterative method for the bootstrapping stage, which maintains the performance for unbounded Hessian.

Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity
Qian Yu
Yining Wang University Texas at Dallas yining. wange dtaggeetlllllle daasalll................. edu
University of California, Santa Barbara Saanyu22uucsb edu
Baihe Huang
Qi Lei
Jason D. Lee
University of Califomia, Berkeley baihe heihe_huann@berreeeee edu
New York University
Princeton University
q1518enyu.edu
Jasondl1princeeton.
Abstract
Optimization of convex functions under stochastic zeroth-order feedback has been major and challenging question in online learning. In this work, we consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds. We propose an algorithm that features a combination of a bootstrapping stage and a mirror-descent stage. Our main technical innovation consists of a sharp characterization for the ppherical-sampling gradient estimator under higher-ordet smoothness conditions, which allows the algorithm optimally balance the bias-variance tradeoff, and new iterative method for the bootstrapping stage, which maintains the performance for unbounded Hessian.
1 Introduction
Stochastic optimization of unknown function with access only noisy function evaluations is a fundamental problem operations research, optimization, simulation and bandit optimization research, commonly known zeroth-order optimization (Chen et al. 2017). derivative-free opti- mization (Conn et al., 2009 Rios & Sahinidis, 2013) or bandit optimization (Bubeck et al.) 2021). In this problem, an optimization algorithm interacts sequentially with an oracle and obtains noisy function evaluations at queried points every time. The algorithm produces an approximately optimal solution after T such evaluations, with its performance evaluated by the expected difference between the function values at the approximate optimal solution produced and the optimal solution. A more rigorous formulation of the problem is given in Sec. below.
Existing works and results on stochastic zeroth-order optimization could be broadly categorized into two classes:
1. Convex functions. In the first thread of research, the unknown objective function to be optimized is assumed to be concave (for maximization problems) or convex (for minimization problems). For these problems, with minimal smoothness (e.g. objective function being Lipschitz continuous) it is possible to achieve sample complexity of Õ(E-2) for an expected optimization error or e, which also a polynomial function of domain dimension
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Lower Bound
Upper Bounds
Bach & Perchet (2016)
Akhavan et al. (2020)
(
O M
O(dT-
Novitski & Gasnikov (2021)
Ours
O MM
O(dT M
Table The dependence of simple regret on (number function evaluations), d (dimension) and
M (parameter describing strong convexity). Our results are highlighted in comparison to the prior works.
d: see for example the works of Agarwal et al. (2033) Lattimore & Gyorgy (0021) Bubeck
et al. (202T):
2. Smooth functions. In the second thread of research, the unknown objective function to be optimized is assumed to be highly smooth, but not necessary concave/convex. Typical results assume the objective function is Hölder smooth of order A: 2 1, meaning that the (k: - 1) derivative of the objective function is Lipschitz continuous. Without additional conditions, the optimal sample complexity with such smoothness assumptions is ((c-(2+d/R) (Wang et al. 2019), which scales exponentially with the domain dimension d.
In this paper, we study the optimal sample complexity of stochastic zeroth-order optimization when the objective function exhibits both (strong) convexity and a high degree of smoothness. As we have remarked in the first bullet point above, with convexity and Hölder smoothness of order A = 1 (equivalent the objective function being Lipschitz continuous), the works of Agarwal al. (2013); Lattimore & Gyorgy (2021 Bubeck et al. (2021) established an ((=T²) upper bound. With higher order of Hölder smoothness, i.e., k = 2 (equivalent to the gradient of the objective being Lipschitz continuous), it is shown that simpler algorithms exist but the sample complexity remains Ó( 3) (Besbes et al.) 2015 AAgaraa et al.] 2010; Hazan & Levy, 2014), which seemingly suggests the relatively smaller role smoothness plays in the presence of convexity. In this paper we show that with even higher order of Hölder smoothness, i.e., k 3 (specifically, the Hessian of the objective being Lipschitz continuous), the optimal sample complexity is improved to O(E-1.5), which is setting Ö(
significantly smaller than the sample complexity of the setting Ó(E 0(=-(2+d/3)) More importantly, when the Lipschitzness of Hessian is defined in Frobenius norm (see condition A1), we propose an algorithm that also achieves the optimal dimension dependency, which fully characterizes the optimal sample complexity.
or the
Summary of technical contributions. We developed several important techniques in this paper to achieve the optimal sample complexity when the objective function is strongly convex and has Lipschitz Hessian. First, we show that when estimating the gradient under a stochastic environment, even with an unbounded action space, it could be beneficial to sample with non-isotropic distributions (as opposed to conventional standard Gaussian, or uniform distributions on hyperspheres). Second, we present a new approach to analyze the bias and variance of the hyperellipsoid -aaiiid--mlliinnbbae based gradient estimators, which enables obtaining sharp bounds with tight constants and strengthens the best-known results in the higher-order smoothness case. Third, we present a two-stage bootstrap-type framework for the algorithmic design, which extends the perturbative analysis in the final stage to the full regime. This extension relies on a non-trivial modification of Newton's method, and we proved its robustness under stochastic observation. We complete the characterization of the minimax regret by deriving a lower bound using the KL-divergence- based approach.
Additional related works on higher-order smoothness. Recent years have seen increasing atten- tion on exploiting higher order smoothness in bandit optimization. Remarkably, it was shown that when the Hölder smoothness condition holds simultancously for both
and 3. the optimal sample complexity can be improved to O( ((55).)). (Akhavan et al.) 2020 Novitskii & Gasnikov 2021). We list our results together with the most relevant work Table While this line of work also demonstrates the benefit of higher-order smoothness in improving the sample complexity, their setting is related but slightly different from what we considered in this work. (See reference therein: Bach & Perchet (016): Akhavan et al. (2020); Novitskii & Gasnikov (2021)). On one hand, the prior work concentrates on projected gradient- like algorithms, which require Lipschitz gradient (i.c.. the k 2 requirement, and we do not). This additional requirement can not be removed by

---

simply replacing the gradient steps with Newton's methods, which can lead to unbounded expectation On the other hand, their results are based on the generalized Hölder condition, which is different from our assumption that the Hessian is Lipschitz in Frobenius norm. Therefore we only emphasize the dependence of d, 7 and M in Table | and omit other parameters. We provide a detailed comparison on the implication of these results in Appendix [A]
in simple regret in the stochastic case I
Our results are also related to a special case discussed in (Shamir 2013). which shows that for quadratic functions it is possible achieve sample complexity of O(e As quadratic functions are infinitely differentiable with bounded derivatives on orders, they are Hölder smooth of any arbitrary order + oo, which could be regarded as an extreme of the results established in this paper which only require k = 3.
Related works on gradient estimators. Gradient estimatiin serves as key building block for stochastic zeroth-order optimization al algorithms. For instance, classical one-point estimator was
proposed as early as in Flaxman et al. ) : Blair (188)). where the gradient (x)) is estimated based on empirical measures of f(x + ru) for some fixed r and i.i.d. uniformly random u on the unit
hypersphere. This was later refined to be two-point estimators, and the sampling distribution of u was generalized to isotropic distributions such as standard Gaussian (e.g., see Agarwal et al. (2010); Bach & Perchet (2016); Zhang et al. (2020)) A majority of prior work focused on the analysis for such estimators under the Lipschitz gradient assumption, where the best guaranteed bound for the bias is at the order of (rr). with a polynomial factor dependent on d. The line of works by Bachh & Perchet 2016);; Akhavan et al. (2020); Novitskii & Gasnikov (202T) also adopted isotropic sampling, and it was shown that with higher-order smoothness of k 3, this bound can be improved to (r²²). The improvement of sample complexity in our work is mainly due to the tight characterization of our gradient estimator, which covers the special case of isotropic sampling and provides bound of
"ppvd in the estimation bias. This strengthens or improves the bounds presented in prior works, and 2(d+2)
a detailed comparison can be found in Appendix A
On the other hand, non-isotropic sampling was used early as in Abernethy et al. (2008), then extended in Saha & Tewari (2011); Hazan & Levy (2014). Primarily, they were used to ensure that the sampling points contained within bounded action set. (Suggala et al.) 2021) showed the necessity of non-isotropic sampling over quadratic loss function in the adversarial setting. In this work, we essentially demonstrated that non-isotropic sampling can be used refine preliminary algorithm by adding a mirror-descent-lig final stage. More recently, non-isotropic sampling was also adopted in Lattimore & György (2023) to optimize convex and global Lipschitz functions.
f(x) denotes the Hessian of f at point æ, while the trace of Hessian is denoted by Tr (z)) This should not be confused with the notation in classical field theory, where V (xz) instead denotes the trace of the Hessian. We use || ||2 to denote vector & norms, and || ||e to denote matrix Frobenius norms. We use La to denote the identity matrix, and 5 to denote the unit hypersphere centered at the origin, both for the d- d-dimensional Euclidean space Rd., We adopt the conventional notations (i.e., O, Ω, and w) to describe regret bounds in the asymptotic sense with respect to the total number of samples (denoted by T").
Notations. We follow the convention of machine learning theory where f²f(x)
2 Problem Formulation
We consider the stochastic optimization problem under the class of functions that are strongly convex and have Lipschitz Hessian. The goal in this setting is to design learning algorithms to achieve approximately the global minimum of an unknown objective function f Rd ER
learning algorithm A can interact with the function by adaptively sampling their value for T times, and receive noisy observations. At each time E [T), the algorithm selects n; E Redd and receives the
'we note that even in the classical analysis of Newton's 's method, which assumes zero-error observations, the smoothness condition was adopted to obtain non-trivial complexity bounds (e.g., see Boyd & additional (2004), Section 9.5.3), implying the non- oon-trivislness of removing the k = 2 smoothness condition. Vandenberghe
In this work, we provided an analysis for our proposed bootstrapping algorithm, which ensures the achievability of bounded expected regret with unbounded hessian.
3

---

following observation,
Vr = f(x))) + w/:
where | are independent random variables with zero mean and bounded variance. Formally, the algorithm can be described by list of conditional distributions where each æ; is selected based on all historical data { Dr free and the corresponding distribution. Then for any 1, we assume that [ Vr Jrce: Φt
and Var[w]] yr Jrst,, æt] S for any & For simplicity, we also adopt a common assumption that the additive noises are subgaussian, particularly, P[[w, > a 1/r rr<c, 2t. < 2e-= for all
and [T]. However, the subgaussian assumption can be removed by adopting more sophisticated mean- mean-estiman estimation methods (c.g., see Nemirovski Yuom (1983); Jerrum al. (1886); Alon et al. [999); Lee & Valiant (2022); Yu et al. (2023a)).
We assume that the objective function f second-order differentiable. Furthermore, we impose the following conditions.
(A1) (Lipschitz Hessian). There exist constant p E (0, +00) such that for all æ; x' E Rdd, holds that f(x) V f(x')llF | S p||æ' - 2//2, where || ||| denotes the Frobenius norm;
(A2) (Strong Convexity). There exists constant M (0, +00) such that for any Rd. the minimum eigenvalue of the Hessian f²f(2) is greater than M.
(A3) (Bounded Distance from Initialization to Optimum Point). There exists a constant R (0, +oo) such that the infimum of f(x within the hyperball ||||| S R is identical to the infimum of (() over the entire Rd
In the rest of this paper, we let F(p. M, R) denote the set of all second-order differentiable functions that satisfy the above conditions, with corresponding constants given by M, and R. We aim to find algorithms to achieve asymptotically the following minimax simple regret, which measures the expected difference of the objective function on and the optimum.
P M, R) == inf sup [[f(xT) - f((e))
A JEF(p.M.R)
where x² denotes the global minimum point of f.
3 Main Results
Theorem 3.1. For any dimension d and constants p. M,M, R. the minimax simple regrets are upper
3 d
bounded by lim supt R(T; p. M, R) T SC.
where C. is universal constant. M, R. the minimux simple regrets are lower
M
Theorem 3.2. For any fixed dimension d and constants bounded by lim in R(T; p. M, R) R) C. standard Gaussian, where C is universal constant.
pz M
when the additive noises W1: WT are
4 Proof Ideas for Theorem 3.1
The proposed algorithm operates in two stages (see Algorithm 4. In the first stage, the algorithm uses small fraction of samples obtain a rough estimation of the global minimum point. We ensure that the estimation in the first stage is sufficiently accurate with high probability, so that in the following final stage, the objective function can be approximated by quadratic function and the resulting approximation eтror can be bounded using tensor analysis.
4.1 Key Techniques and The Final Stage
We first present the key steps of our algorithm, which relies the subroutines presented in Algorithm i.e., GradientEst, BootstrappingEsst and EsssianEst. These subroutines estimate the (linearly
3
If the variances of w,'s 's are bounded by different constant, all our results can be reproduced by normalizing the values of f.

---

transformed) gradients and Hessian functions of f at any given point by sampling the values of f on hyperellipsoids. The key ingredient our proof the sharp characterizations for the biases and variances of the GradientEst estimator, stated in Theorem
Algorithm 1 GradientEst
Input: n.
Z is d X d matrix, return estimator of fV
for < 1 to n do
Let us be point sampled uniformly randomly from the standard hypersphere 5d
Let 1/+, y be samples of f at a + Zuz and x Zuk. respectively, let 9 (y+ 1/ y
end for
Return 9 E 1
Algorithm 2 BootstrappingEst
Input: 2,7, 72
Goal: estimate f(x) coordinate wise with (Ind) samples
Let G1; Cd be any orthonormal basis of RRd
for k - to d do
Let kk+ V-, each be the average of n samples of f at a + reg and æ - rei respectively
Let m& (y+ 2/2
> Estimate the kth entry
end for
Return m {mx keEd
Algorithm 3 HessianEst
Input: 2,
> Goal: estimate f(x coordinate wise with O(nd²) samples
Let e1...., ed be any orthonormal basis of TRd
Let be the average of n samples of for + 1 to d do
Let k. y-,k each be the average of samples of reg, and æ reş respectively Diagonal entries
Let HRE (y+ y- for l. +- + to dl do
2y)/r²
Let HRE His be the average of samples of (f(æ + rex + ree) f(a ret rez) b Off-diagonal entries
f(x: + re# - ret) - f(x rey + rez))/4r2
end for end for
Let llg = (H1 ( (esee and il be the matrix with same eigenvectors but with each eigenvalue À replaced by max(A, (A, M) Return 1/
b Projecting to the set where и M Ia is positive semidefinite
Theorem 4.1. For any fixed inputs x, Z, n, and any function satisfying the Lipschitz Hessian condition with parameter p. the output 9 returned by the GradientEst subroutine satisfies the following properties
XHPva
[ ZV
(2)
2(d +
Tr (Covi]))) <
2d [V)(() +
22
18n (x12)2+
d²
d²
2n
where Az is the largest singular value of Z.
Remark 4.2. Inequality (2) provides sharp characterization for the bias of the gradient estimator, as il can be matched for any Az and d with cubic polynomial f. Inequality 3 is sharp in the asymptotic regime when both V and Az approaches zero.
We also provide rough estimates on the high-probability bounds for the BootstrappingEss and the HessianEst functions. Specifically, we show that their errors have aab-Gaussain tails in distribution, stated in the following theorem.
5

---

Theorem 4.3. For any fixed inputs I, n, any function f satisfying the Lipschitz Hessian condition with parameter P. and any variable K >> O, the outputs mn and H returned by the Bootstrapping and the HessianEst subroutine satisfy the following conditions.
K
[| - v](2))122 2 KJ S 2exp
(4)
3dp2rt
+
12d
1
K²
P H -ー
2 K| S 2exp
(5)
2dl
p2
+
144 nr
We postpone the proof of the above theorems to Section 4.2 and Appendix how these results are used in the algorithm.
C
and proceed to describe
For brevity, let e - ęå d be the minimax regret aim to achieve, and let zg denote the estimator M
a stored at the end of the first stage. The role of the final stage is to ensure that if f f(x") is sufficiently small with high probability, the final result of the proposed algorithm achieves the stated simple regret guarantees. Formally, we require the following achievability result from the Bootstrapping stage.
Theorem 4.4. For any fixed p, M and R, the result returned by the first stage of Algorithm 4 satisfies
lim T-000 (..(
sup
[(((xx)) - f(xx)) /e=0.
(6)
Note that the above condition implies that f(xg) - f(x*) concentrates below o (ci)) which is
weaker than the O(e) rates stated in our main theorems 3 The bottleneck of the overall algorithm is
on the final stage, and one can achieve equation (6) using any suboptimal algorithm with an expected simple regret of () For example, one can run the suboptimal algorithm twice, estimate their achieved function values by averaging over o(T) samples, and then choose the outcome with the smaller estimated function value as Zg. In the rest of this section, we prove Theorem 33.T assuming the correctness of the above theorem. A self-contained proof for Theorem 4.4 is provided in Appendix E
Before proceeding with the proof, we provide high-level description of the algorithm in the final stage. At the beginning, we perform a Hessian estimation near æy using the HessianEst subroutine with (TT) samples. From Theorem 4.3 our choice of parameters results in an expected estimation error of o1) for sufficiently large T.
The algorithm proceeds to find real matrix Zh, which essentially serves as linear transformation on the action domain such that the Hessian of the transformed function is approximately the identity matrix. Note that the projection step in the HessianEst function ensures the eigenvalues of the estimator are no less than M. There is always a valid solution of Z.-
Then, estimate the gradient at ØB using the GradientEst subroutine, which samples hyperel- lipsoid with a shape characterized by ZH. We chose the hyperellipsoid sampling in the final stage due to its superior performance in the -rall-gradient regime compared to coordinate- wise sampling. In contrast, the coordinate- sondinntte-wieeeeee wise estimator is used in the bootstrapping stage to eliminate the depen- dency of the local gradient its bias vtrrina tradeoff, which is beneficial for the non-asympiotic analysis. Particularly, we scale the hyperellipsoid with carefully designed factor (see the definition of variable rg)) minimize the estimation error. Then, the remaining steps can be interpreted modified Newton step, which essentially approximates the global minimum point with a quadratic approximation.
The analysis our proof relies on the following proposition, which is proved in Appendix D
Proposition 4.5. For any given point Uy and any function f that satisfies strong convexity and Lipschitz Hessian, let à & ag (V2 ((x)) -1 [VV and f(x:) denote the quadratic approximation
Wiih more sophisticated analysis, this concentration requirement can be improved to only requiring a similar upper bound of o (cb However, we choose equation 6 provide simpler proof, as it does not affect the asymptotic sample complexity.

---

Algorithm 4 An Example Algorithm to Achieve the Minimax Rates
Input p,
Let æ = 0
The First Stage:
for <- 1 to [ do
Let n'm
To.
10a
74 1102 J. I' =
Runa
8
111
144 Par
Let m Bo Tm Rm), (,n) 1l HessianEst(ar, TH R4))
Let H denote the matrix with the same eigenvectors of H but each eigenvalue À replaced by
max X, m²) choose m² to be the smallest value such that || - S M..
P
Let a = a H m
end for
The Final Stage:
Let nz = I TH 10a 1.
d
1igh"
TH
Let Ā HessianEEs((r; ru, m1), Zu be any symmetric matrix such that 73 -T-1, and Azn be the largest eigenvalue of Zμ
Let Z = =r λz 9 GradientEst(2;; r=-1)-1---- g Project to the L2 ball of radius M i.e.. r = r min(1, -||l|12 }
Return
{x - TV (xx)(= 3) we have the following inequality for all a with || - œ8l12 S M
f(x)- - 1" (2 12p(f(xx) f*)
M
Furthermore, if is generated by the final stage of Algorithm f with any parameter values that satisfy ng 2 d8, 2 61p²d" and the first-stage ousput is set to Eg, then
14d2
52d
82p
3dp
E [(x) anp S
+
(f(xn) - f(x"))
( ( f(x)))
(8)
M
Tig
M
Mn.
Now, we use Proposition 4.5 prove the achievability result.
Proof of Theorem 3.1 given Theorem 4.4
First, recall our construction ensures that ||>> 2al12 S
M. Inequality can always be applied and we have
p
sup E 2f(x) + 12p(f(xx) ( SEF(P.M.R
p, S
M
Then, when I' is sufficiently large, the conditions of 8 holds and we have
28d2 p
104d
176p( ((r)) - 5
R(T:p, S sup (eF().M,R
E
(f(mn) f(x*)) +
2
ng
M
6dp3
Mngg
Note that inequality (6) implies that E (f(s)) - f(x*)] o(e
3) and we have that
uu ng. - oT t). The RHS of the above inequality is dominated by the last term. Hence,
ódpēT
lim sup M(T: p. P, M, T lim T
=
T+x
Mn
M

---

To complete the proof, we show that the proposed algorithm samples the function values of f at most T times. In the first stage, both BootstrappingEst and HessianEst are executed once per loop, with BootstrappingEst requiring at most 2dn S T
5 samples and HessianEst requiring at most 2d nu S T samples each time. Therefore, the total number of samples used the first stage bounded by [T]] 1 7 5 - _ In the final stage, we make one call to both HessianEst and GradientEst, which together require (= + 2ng S 2T samples. Thus, the overall number of 47
samples is bounded by 5 which ensures that it is no greater than T 1.
4.2 Proof of Theorem
To prove inequality
2 we investigate the following function
d
G(r: e Eu--Dni((Sa))
(f(x ru) f(x (ru))u 2r
where Uni denotes the uniform distribution St-11, Recall that in algorithm we have Elg] = rG æ) = rla for some r E (0, +00), and by differentiability we have Vf(()) = lim G(2; æ). Under this condition, we can bound ||ق|ع] - (x)) by integration, i.e.
E و - f =r G(r;z)- - lim G(zzz) 2-0++
rr r f dz
G(z
dz.
(9)
Note that G(2; æ) can be written into the following equivalent form.
Sga-1 1 (f + zu) f(x - zu) )AA
G(2;
Ssa-1 dA
where the integration is with respect to u over the surface Sd-1, and dA is the vector surface element, ie., with the magnitude being the infinitesimally small surface area and the direction perpendicular to the surface (pointing outward). The differential of G(z; x) over can be written as
d dz
fga-1 02 2z
(d (f (xx + zw) - f(x - z4))) dA
G(2;a))
Jsa-1 |A
sga-1 22 (f(x zu) f(x - =2)) dA
Sga-1 ||A l2
Ssa-1 25 u (V zu) Vf(x z4)
+
S |dAl22
The gist of this proof note that for any to the normal vector of the hypersphere at the same point), so the second term in the integral above on the numerator can be written
have u and dA are parallel (i.e., u is parallel
/ S 2z u uV zu) + Vf(x -2u) dA.
Hence, by divergence theorem, we have
d G(;;z)
Jga-1 |dAll2 (NL. V.
1
d
22 la (f(x +x++00+00 zu) f(x (lx))))
(Vf + V zu))
dV
2z
d
Sn u Tr (2 f(x + zu) [2f(x 122 zu dV
(10)
1ga-1 dA
where Bd denotes the standard hyperball.
8

---

Now consider any unit vector Let we denote the reflection of u with respect to the hyperplane orthogonal to e, i.c., Ue 2(u e)e. Because the hyperball B is invariant under the reflection - Ue, equation (10) can also be written as
d G(zz))
d JB. ue Tr(V? (a + zuc) - v2 - 2uc)ddV
(11)
dz
Ss |dA||2
Hence, by averaging equation 10 and we have
d G(zz))
d BB Tr f(x + z4) v2f(E zu
de
e
Ssa-1 |dA|2
d Spa the Tr f(x + zue)
v25(2x - zuc)
Ssu ||
Ba eTr(v2 + 24) V2 f2 zue))
4
1ga-1 |dA||2 2
d Sn -u e TT f(x zu) zue)ddV
+
(12)
Sga-1 dA
By the Lipschitz Hessian condition and Cauchy's inequality, the difference between the differential terms above can be bounded as follows.
Tr ( f(x + zu) f(x = =2e))] & V =u) - f25(2 + zue)l
S pv zue @zpvdlu= el.
(13)
Consequently,
d
zpdv d J (u e) dv
zpVd
G(2;z))
<
dz
Sga-1 ||A|||
d+2
Note that e can be any unit vector. We have essentially bounded the &a norm of d da G(; i.e.,
zpvd 2
G(z:))
As mentioned earlier, when Z rla inequality is obtained by applying this gradient- norm bound to inequality (9)
For general input matrix Z, we can view GradientEst as subroutine that operates on the same function but with linear transformation applied to the input domain. Formally, let f'(y) e f(x + Az (y ())) We have that f' satisfies the Lipschitz Hessian condition with parameter p as well. Therefore, inequality (2) can be obtained following the same analysis by replacing f with f and Z with AzLa-
2
Now we present the proof for inequality 3 Formally, let w4, w be independent samples of additive noises. Then the trace of covariance matrix of ğ can upper bounded using the second moments of single measurements.
< E Eu--Uni( (dd")(((ddd)) 1,,,, w [(0)² (f(x + Zu) - -fxx - Zu) + w - w-)²
Tr (Covlg)
n
d
4m E
Unif 1) [f(x + Zu) f(x - Zu))² +
(14)
The identity above uses the fact that additive noises unbiased and have bounded variances.
Note that from the Lipschitz Hessian condition, we have that
1 fx Zu) f2(x Zu)l S p p2%.
1

---

where f2 is the Taylor polynomial of f expanded at æ up to the quadratic tenms. Consequently, inequality (14 implies
d²
1
2
Tr (Covlg))
-
E
1f2(xx + Zu) f2(2 Zu)l +
+
4n
3
d²
2
12Zu vf(x)] _012
E
+2
4n
d²
(3011)
2
E
2. 122u vf(z)) +2 (3.12
+
4n
2d |ZVf(>))
&
d2
(p13)²
n
18n
2n
where the expectations taken of Unif(SA-1), 1) and the last equality is due to the well-known fact that E [wuT] La-
5 Conclusion and Future Work
In this work, we achieve the first minimax simple regret for bandit optimization of second-order smooth and strongly convex functions. We derived the matching upper and lower bounds and proposed an algorithm that integrates a bootstrapping stage with a mirror-descent stage. Our key technical innovations include a sharp characterization of the spherical-sampee sampling gradient estimator under higher-order smoothness conditions and a novel iterative method for the bootstrapping stage that remains effective with unbounded Hessians.
While these advancements settle the fundamental problem of optimizing second-order smooth and strongly convex functions with zeroth-order feedback, the techniques and insights presented in this paper also pave the way for further research in this domain. One interesting follow-up direction is to generalize analysis to the online setting for the average regret metric. Additionally, investigating the fundamental tradeoff between simple regret and average regret could yield valuable insights for task-specific algorithmic designs.
Acknowledgement
JDL acknowledges the support of the NSF CCF 2002272, NSF IIS 2107304, and NSF CAREER Award 2144994.
References
Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. pp. 263-273, 2008. 21 Annual Conference Learning Theory, COLT 2008 Conference date: 099-07-2008 Through 12-07-2008.
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Colt, pp. 28-40. Citeseer, 2010.
Alekh Agarwal, Dean P. Foster, Daniel Hsu, Sham M. Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. SIAM Journal on Optimization, 23(1):213-22) 2201322202222 2013.
Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Exploiting higher order smoothness in derivative-free optimization and continuous bandits. Advances in Neural Information Processing Systems, 33:9017-9027, 2020.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137-147, 1999. ISSN 0022-0000. doi: http:::/doi..rg//0000000//////// 199. 1997. 145. URL https: www.::/wwweeeeii..ooommo rect com/
10

---

Francis Bach and Vianney Perchet. Highly-smooth zero-th th order online optimization. In Conference on Learning Theory, pp. 257-283. PMLR, 2016.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 2277:4422, 2015.
Charles Blair. Problem complexity and method efficiency in optimization (as nemirovsky and db yudin). Siam Review, 27(2):264, 1985.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex optimiza- tion. Journal of the ACM (JACM), 68( 6834))1-35, 2021.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pp. 15-26, 2017.
Andrew Conn, Katya Scheinberg, and Luis N Vicente. Introduction to derivative-free optimization. SIAM, 2009.
Abraham D. Flaxman, Adam Ta uman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the Sixteenth Anmual ACAM Symposium on Discrete Algorithms, SODA '05, pp. 385-394, USA, 2005. Society for Industrial and Applied Mathematics. ISBN 0898715857.
Elad Hazan and Kfir Levy. Bandit convex optimization: Towards tight bounds. Advances in Neural Information Processing Systems, 27, 2014.
Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combina- torial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. ISSN 0304-3975. doi: http.///wweeeeeeeeeeeee////////. / www.
URL htttst
com/
Tor Lattimore and Andras Gyorgy. Improved regret for zeroth-order stochastic convex bandits. In Conference on Learning Theory, pp. 2938-2966 PMLR, 2021.
Tor Lattimore and András György. A second-order method for stochastic bandit convex optimisation. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings Thirty Sixth Conference Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 2067-2094, PMLR, 12-15 Jul 2023. URL httpt:tt:////t ptttpp::/prroceed: ngs. mtt. ltt. http://aaammrrrea...mo .htmmmml..l.mmm.mm
Jasper C.H. Lee and Paul Valiant. Optimal sub sub-gaussian mean estimation in IR. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 672-683, 2022. doi: 10.1 (00////OSS2999.222...0
A. Nemirovskii and D. Yuom. Problem Complexity and Method Efficiency in Optimization," Wiley, 1983.
Vasilii Novitskii and Alexander Gasnikov. Improved exploiting higher order smoothness in derivative- free optimization and continuous bandit. arXiv preprint arXiv.2101.03821, 2021.
Luis Miguel Rios and Nikolaos V Sahinidis. Derivative-free optimization: review of algorithms and comparison of software implementations. Journal of Global Optimization, 12:1 2013.
Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Geoffrey Gordon, David Dunson, and Miroslav Dudík (eds.), Proceedings of the Fourleenth International Conference Artificial Intelligence and Statistics. volume 15 of Proceedings of Machine Learning Research, pp. 636-642 Fort I Lauderdale, FI., USA, 11-13 Apr 2011. PMLR. URL https: http:://///.cceiiings... mlr www.s//essssvv.... wttpp///e/e.///aaaaaaaaaaaa////a www.alaaallllaaaaam.a.aa..a.a..a

---

Ohad Shamir. On the complexity of bandit and derivative- free stochastic convex optimization. In Shai Shalev-Shwartz and Ingo Steinwart (eds.). Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pp. 3-24, Princeton, NJ, USA, 12-14 Jun 2013. PMLR. URL httph:t htttps://proceedings. ml
html
Arun Sai Suggala, Pradeep Ravikumar, and Praneeth Netrapalli. Efficient bandit convex optimization: Beyond linear losses. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp.
4008 4067. PMLR, 15-19 Aug 2021. URL pptpe///dgoooooegggg.. mlm.r.r...... www.r.pres//vl44
aungalalla. html
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Yining Wang, Sivaraman Balakrishnan, and Aarti Singh. Optimization of smooth functions with noisy observations: Local minimax rates. IEEE Transactions on Information Theory, 65(11) I): 7350-7366, 2019.
Qian Yu, Yining Wang, Baihe Huang, Qi Lei, and Jason D Lee. Sample complexity for quadratic bandits: Hessian dependent bounds and optimal algorithms. A. Oh, Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 35121-35138. Curran Associates, Inc., Files//pperr2023/ 2ere://98.22222fff00000222222220
2023a. URL https::/prroceednss... www.riep....pppppeeeeeo
Qian Yu, Yining Wang, Baihe Huang, Qi Lei, and Jason D. Lee. Optimal sample complexity bounds for non-convex optimization under kurdyka-lojasiewiizz condition. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 6806 6821. PMLR, 25-27 Apr 2023b. URL https://
www. httpa//.........reee///////////. html
Yan Zhang, Yi Zhou, Kaiyi Ji, and Michael M Zavlanos. Boosting one-point derivative-free online optimization via residual feedback. arXiv preprint arXiv22010.03378, 2020.
12

---

A Detailed Comparison on Different Smoothness Conditions
In relevant line of work, the higher-order smoothness of the objective function in the case is characterized by the following generalized Hölder condition.
[(z) - [()) (z)))(z =) - x) (V² (=
-=
L||= = 2x
Note that the p-Liipschizz Hessian condition in our work implies an Hölder condition with parameter L == 6- A direct application of the works in Table I requires order-wise larger sample complexities in our setting on top of the additional A: = smoothness condition. On the other hand, the L-Holder condition implies
O(v ((V)))--ipsshitzz Hessian. Hence, a direct application of our algorithm order-wise improves the sample complexity in the setting of generalized Hölder condition in polynomial factor of d as well.
In terms of the characterization of gradient estimators, the prior works of Bach & Perchet (016));
Akhavan et al. (2020); Novitski & Gasnikov (202I) used isotropic sampling over a bounded set of radius r and presented upper bounds on the estimation bias of ((r²)) O(Ldr",, and O(L (Lv/dr?), respectively. In this special case, our Theorem 4.1 implies an upper bound of (prr? /vd), and similar the above analysis, this bound strengths the bounds in prior works.
B Proof of Theorem 3.2
To illustrate the proof idea, we start with the case of d = 1.
B.1 Illustrating example: 1D case
The gist of our proof is to construct pair of hard-instance functions that need to sufficiently distant from each other to avoid trivial optimizers with low simple regret. We also require them to be sufficiently close each other so that they indistinguishable without sufficiently many samples. These requirements are captured quantitatively in the following result, which is proved using an analysis of KL divergence. Here assume their correctness and focus the construction.
Definition B.1. For any (Borel measurable) function class Fü and any distribution p defined on Fi. we define the uniform sampling error be
P P f~ inf f2e)
We also define the maximum local variance to be
V sup Var y~p Marr~plffle [(x)]]
Lemma B.2 (Restatement of Proposition in Yu al. (2023b)). For any sampling algorithu to
achieve an expected simple regret of > O over a function class Fu. if P2efe 2 e effor some universal constant e E (0, 1), and the observation noises are standard Gaussian, then the required sample complexity achieve minimax regret of is at least Q(1/V).
We construct our hard instances using the following function
+ (sin (1)z)
if (-T,, 3T] if x E (-37, -T otherwise.
g(x)
cos r
Some key properties of gxx be used are that its differential g' gx(x) is 1-Lipschitz, and have Ig' (x)l < 1 for all æ. Our hard instances consist of two functions. We define
/ g(2)d2,
f1(x) 2x² + yo
2/20
f2(z) = 2x² + 9(2)d2,
13

---

where yo. zo are normalization factors given by Mo xVT. 400
The normalization factors are chosen to satisfy the Lipschitz Hessian condition and a maximum local variance bound required for a KL-divergence based approach presented Lemma B.2
yo
Specifically, the choice of Zg and the fact that g' (z) is 1- 1-Lipschitz imply that both fi and fo satisfy the Lipschitz Hessian condition. Then because the absolute value of integration of g(x)) is bounded by 2T,, one can show that the maximum local variance for the function class {/1, f2] is no greater
than y² T for the uniform prior distribution, which to be used show the sample complexity lower bound.
We first check that both fi and f2 are within our function class of interests. Note that both fi" and f2 (a) belong to the interval 2.M-
3 ug 2M =0 M > O, we have both (a:) M and (x) > M for all x for sufficiently large T. So the strong convexity requirement is satisfied. On the other hand, consider any global minimum point x" of either fi or f2. Because of their differentiabilityy we must have (z) 0 or f2(x) O. Note that for z, we have g(x)] I 2, and
From the fact that limy Mg 0 and 26
fi(x) 2M +
yo
20 30
yo
f2(x) 2Mx
30
We must have |a*| Zn /M, where the RHS is o(1) for large T. Combined with strong convexity, this inequality implies that assumption A3 holds for both functions. To conclude, we have proved that S1, /2 F(, M, R) for sufficiently large T.
Now let
1
yo Zo
and
2 apply Lemma B.2
Note that
128M
p
lim lim 7-500
128 3 M
The quantity e exactly matches the lower bounds we aim to prove. Therefore, it remains check that the required condition on uniform sampling enrors in Definition B.I are satisfied.
Formally, we need show that (0) inf [u(x)) 2 4e for ts E {1, 2), that the uniform sampling error Pae under uniform distribution over FH is lower bounded by and Lemma B.2 can be applied.
Without loss of generality, we focus on the case i = 1. Note that (x) S 2M
vo. for all
4x3
mw00 0). Therefore, have
f(x) /1( < f(0)2r + 2"
sup
=E[ =E(-<xg.0]
90
30
x +
2M
200
4x
for x E [-Tz0, 0]. and limy To = 0. Consider any sufficiently large such that 4-g
2o S 2M, we
can choose x 2no 2M+
No for the above bound, which falls into the interval [- 0). Then
42
have
inf (1()) 2M +
yl0
x
2x0
12g
90
2
$ $h)
1/0
2
2x00
2M
Mo 4mg
(h) 4e.
We use this inequality to lower bound the minimum sampling error. Note that fi is an increasing
function for 2 0 and inf, fi(x) inf, f2(x). We have fi()) 2 inf, f2(z) + 4e for 2 0.
14

---

Following the same arguments, we also have f2(2) > infz fi(z) + 4e for I 0. Recall the definition of uniform sampling error Definition B.1 We have essentially proved that Par 2 3 According to earlier discussions, this implies that the minimax simple regret is lower bounded by
c=
Ω
M
B.2 Proof for the General Case
The generalization of the earlier 1D lower bound is obtained by constructing set of hard- hard-instance instance functions where the optimization problem over this subset consists of d binary hypothesis estimation problems, each identical ID construction. Formally, for any & = (81, 82, .. 84) {1, and any input (I()); F(2), -.. ((d)), we let
fe(x) = (o)
One can verify that fo E M, for all s for sufficiently large T.
Note that the simple regret for the above function class can be written as the sum of individual
terms Σj=1 (Ja, (x( inf, Sz, (x)). As proved earlier, the expectation of each term associated with any index j is at least ?
Ah M
even if all entries of except sy is known. Therefore, the
[nprr 3 M
total expected regret lower bounded by
C Proof of Theorem
We the following elementary facts, which versions of well-known properties of subgaussian and subexponential distributions in |eershyni (2018), but with explicit and possibly improved constant factors, For completeness, provide their proofs in Appendix
Proposition C.I. For any real-valued zero-mean independent random variables 21, -i Zko if
K2
F|a 2 KJ < 2exp
(TO3)
Aj E [b], (0,+00),
(15)
03
for some T1, ..y The then
K²
Σ 2j
K
S
2exp
AA (0, +00).
(16)
4
Proposition C.2. For any real-valued independent random variables 21, 2k. if
K
Pl 2 KJ <
2xp
Aj E [k], K E [0, +00);
(17)
Jj
for some positive on, The then
K
P
24
> KKKK
< 2exp
A E [0, +oo).
(18)
3 f===100
Proof of equation We first prove the bound vise. Consider any my which contains summation of 2n independent subgaussian variables. By Prop. C. we have that
(-
K2
PP [|m
E [me]]
K] < 2exp
V K E +00).
(19)
2/nr2
15

---

Then, by the Lipschitz Hessian condition, the bias for each entry is bounded as follows.
E
[mm]]
f(x)
S p
(20)
Oor
where 2y denotes the kth entry of æ. Hence, each
e my
do f(x) is subexpoential, i..,
a
m1
((x)
K2
Img - E |mx]l 2
B [m
((x)
1
$ I - E [mm)]
2
pr?
6
(max (K prp no,,,
$ max
2exp
2/nr²
K22
S exxp
(21)
p
By the independence of my is, we can apply Prop.
C.2
to the inequality. Therefore,
Pllm - vf(x)]2 2 KJ = IP
my
f(x)| 2 K2
Ork
K
S 2exp
A K E +00)
(22)
3dp
12d
Proof of equation (5). We first provide the entry-wise bounds for the intermediate estimator Ho Each diagonal entry HR contains the weighted average of 3n subgaussian variables. Conditioned on any realization of y. which is shared among all diagonal elements, Prop. C.I can be applied for the rest of the 2n terms, and provides the following bounds.
(-8/
K2
H| HE yll 2 K] S exx
(8/nr/
E (0,
(23)
Then, because the off- fiagonag entries are independent, we have the following bounds for any j #
(-
K²
Hi E[H,u]| 2 K] < 2exp
A E (00).
(24)
1/nr4
Hence, similar to the earlier proof steps, Prop.
C.2
implics that
K2
P [1 E Holvil1 > x²]
< 2exp
6d(d + 3)/mr²
K2
<
2exp
(25)
24d / //r2//r4
Now, we take into account the estimation bias and the error of By Lipschitz Hessian, it is clear that
pr
if otherwise.
Hss dx, Oxx
f(x) <
Y2
pr
Hence,
< 2dpr
11 - v2
(26)
3
16

---

Furthermore, note that H(Ho] - E Ho 2(y f(x))[a/r² where Ia denotes the identity matrix.
The subgaussian condition and Prop. i.Ily that
Kr²
pl - E[Holvlle 2 K]
P ly
f(x)) 2
2vd.
K²
S exp
K +00).
(27)
8d/nr
We can combine the above bounds using triangle inequality and the union bound. Specifically, from inequalities
and 27 we have the following bound for any K /2drr
3
V2dpr
Ho V
f())))
K
|1 E[Aolll: 2
K
1
22pr
IP
[.0 ELHolv/ll
K
3
3
V2dpr
I
|| B|Holbllle
2
K
2ddrr K
K
Zdor
exxp
+ 2 exp
54d? 5/d22/10 //rr
72d/nor
Utilize the fact that any probability measure is no greater than 1, the above inequality implies that
max { K /ddr .03)
P - - 2 K| s 2exp
128d? /
K2
< 2xpp
AK E [0, +00).
(28)
2d p2 +
144d
Finally, the needed bound for A is due to the projection to convex set where the target V2 belongs. Hence. the distance is not increased w.p.1, i.e., we always have || - 22 f(x)) <
| fax)le.
D Proof of Proposition 4.5
Inequality 7 is derived from the following approximations, which are due to the Lipschitz Hessian condition ZB.
1
f(x) f(xu) + f(x) f(xz)
6 zull2
(29)
f(x*) 2 f(x)) + f(xx)) - F(xB) - 6 1|"0"- =x113
(30)
Noting that f(x²)= 2 0. the above inequalities imply that
f(x) f(x*) - f(x)) + 11 - an 3 + p1|22*
2pp
(31)
||00 mn11 2(((a)) f((m)) Hence, it remains to provide an upper
By strong convexity, we have
bound for _l 2p l..
When |
>ppl2 I / ø1/2, we apply the condition ||x - ænl12 2 S M
to obtain that
p
-||k=
æ 2
< !
1
M|
-
213 5 f(xx)
2
17

---

where the last step is due to the strong convexity of f. This implies inequality 77.
For the other case, we have | æBl12 2 v -112. We replace the variable æ in inequality (29 with x to obtain that
f(x²) S f(t) 1 f(xn) - f(xx)) + 60122 - x
(32)
By strong convexity,
1 M DB 11
f(xz)) 2 2
(33)
and by triangle inequality, we have that
1 M
| - xB 12 S |
+ || - Øb12 S
1
v3 P
Hence, to summarize,
1
f f(x") 2
M - xg 11
6v3
and the needed result is obtained by applying the above to inequality (1).
Now prove incquality (8) The proof consists of three steps. For brevity, let H & f(F(z)) and FB
f1-12- 9. We first prove that
x.
f(x) S f(x+)(+++))))) (f(zs)
M3 f(zz))
(34)
8p²
We shall repetitively use the fact that || 5 S 22 for any = E Rd, which is due to strong convexity. When both f(x+) and f(mn) are no greater than M
8p2, both ||+ 2112
and ||ا| z are no greater than M. By triangle inequality, we have || =Bll2 I M. 2p-
Recall the construction of æ, which is identical to x in this case, inequality (34) clearly holds. Otherwise, note that x: belongs to the line segment between Ty and x.. By convexity, we always have f(x) max( (ann)) Recall that in this case, f(xn) 2 f(x+) can only hold when a
f(zz) 2 213 8p2. we have f(xx) I 1 (f(zz) 8p²
f(x+)+1 (f(xz) 2 Ma3 max{f((4)) (xx)).
8p3
which implies inequality (34).
As the second step, we prove that
7
p
26d
3dp
E (((x)) σB
I
+
f(x8) +
(35)
2
T2g
Mng
Note that the estimation error of ā can be decomposed into two terms, i.e.,
x ã = H ( - -
= (1 Hー + -z-
where the first term is due the error of the Hessian estimator, and the second mostly contributed by the GradientEst estimator. We apply the AM-QM inequality to their quadratic forms, i.e..
f(x+) = b ( -
a))
< <1 11m (2V
-9)1
2 ||
= -
2 f(z))(z)) - -912.
Fg
where AzZ Hg are defined in Algorithm 4 and || denotes the spectrum norm By theorem 4.1 we can first take the expectation of the above bound conditioned on any realization of H. Specifically,
E 12V 011 H, vn
< fVf( - E [ H æn
11. Tr (ov
2
[9 fi (1
r- rgova
2d ng
&
(pri)²=
d²
+
22 S (IDR)
2(d + 2)
18ng
2ng
18

---

Recall the definition of Z, we have
||
$ V (Vf(azg) f(x)))
X
Hence, by our choice of rg. in Algorithm 4 and note that \zn [(x+) H. FB|
M is implied by strong convexity,
H (H- H
|| H 112 3dp
2d
2d ||
1
) V
(T
2Tm
4M
| (H 1 - (T H 112 +
2d
||
H
AT 211²)
fgg
+ +1 f $12
3dp
2d
1
4M
27n
To characterize the above bound, we first note that the singular values of H A equals the cigenvalues of - than M, by triangle inequality, all eigenvalues of (Ia + A 1 (H fI +) are bounded within
La + f *H H 4. As the eigenvalues A are no less
||H-A A le 1
||8 [1l- Hence, we have
M
M
H H|E
| A +1p 1+
M
Similarly, bounds on the singular values of H A + imply bounds on the eigenvalues of H f Ht. i.e.,
H HII
M
Therefore, we have
| A1IF)
2d
||
AlIF)
)
2)
[(x+)) H, DB
S
+
1+
|| 1 1 fx
M
ng
M
H
3dp4
2d
1 1+
1+
M
4
27
Now that the above bound is simply a polynomial of ||
H
l|e.
We can use Theorem 4.3 to
obtain IP | H F
then apply a direct integration. We utilize the assumptions in the statement of proposition obtain simpler estimate, expressed follows.
exp
k²
p6 /n
7d
p
26d
3dp
E f(++) x
|| -
M2nn
ngg
Mn
Then, inequality 8 is implied by the definition of f.
For the third step, we observe that the earlier proof steps imply that
E
(1x) pm <
7dP
26d ng
+ (f(mm)
M3 8p²
f(w))
3dps gm
(36)
Mn
and it remains characterize f(xg)) To that end, we reuse inequality
32) and which implies that
f(æn) < (xx)))) (xx")) when ||e æall2
aM For the other case, we have || ||
|
3M
2p
2p
We instead let x, 2B +
3MM (ā xB)) and the Lipschitz Hessian condition implies that 2pll#
1 11 iz 2x112. -
f(x²) ) S f(Ø)) < f(xz) - f(æz) + f(xx))
19

---

By convexity, we have f(m)) f(x,,)
V 2p|aa -ul--=all (mm)) which can be applied the above
3M
bound. Then, together with inequality (33)
and the condition of || TBl12. we have
f(az) ((x))) V 2p|| - 2BI22
3M
(((xs)
M
|| FB 12
(37)
3
3M
f(00))
2pl C TBl12
3 M
f(xB)
4p
To summarize, the following inequality holds in both cases.
f(wg) S max 2([(2))) (ax"))
Sp
(f(zz) 1(x2))
(38)
3M
To apply inequality (36 we use the following implications.
8p
f(æz) I 2(f(xz)) - f((x)) + (f(Øg) f(x²))²
3M
1 f(xx)) 8p2
Ma F(xx) S
8p
(f(x)) - f(x
M
Then, the derived inequality be simplified using our assumptions ng and fug-
E Remaining details for Theorem 3.1
To complete the proof, we essentially need to prove Theorem 4.4 To illustrate the main ideas, we start with analysis in simplified setting where estimation errors for the BootstrapingEst and HessianEst functions are zero. Then, we show how the proof steps can be modified to have the errors and uncertainties incorporated.
E.1 Analysis for the zero-error case
We prove that when the estimation errors are set to zero, the first stage of Algorithm reduces V (zzt) to vector of bounded length in boundedly many iterations. This is summarized in the following proposition.
Proposition E.I. For any fixed parameter values p, M, R, let {ZthieN, be sequences defined for any E Flp, M, R),, such that 21 0 and (zt+1 zi) equals -H where He is matrix that has the same eigenvectors of f22)). with each eigenvalue replaced by max X, m.). and my being the smallest value for || ((x))] I /. There exists an explicit function M. < 5R pRp 2/M2 + such that V fzz) I M² holds for any f and any t 2 T(p, M, M.R). R).
Proof. For convenience, let P; (V= and r, & -H. To investigate the evolution of gradients, integrate the Lipschitz Hessian condition and obtain that
[V/[(z+1) - Vz(2)) v (Z.) S 501mm111.
(39)
From the definition r,, if [ < M/p. we have
M
[V - 5 2p
(40)
Note that by strong convexity, when the above bound holds,
||V[(=+))|l>
M
M
<
(41)
M
2p
p
20

---

Hence, once ||rlle reaches below M/p for some to, our desired bound on [ remain hold for any > to. Therefore, for the purpose of our proof, we can focus on the case where || > M/p and show that this condition can only hold for boundedly many iterations.
Consider any fixed function in our proof is to show that
F(, M, R),, let xx" denote its global minimum point. A crucial step
(x* -1) Te 0.6| r
(42)
For brevity, let B denote the minimum eigenvalue of He, and f denote the following quadratic approximation.
- f(z) - f(z)) + (æ =z) + 52(x - ( z1).
We apply the strong convexity condition at point y _ 1 1.. 0.43HI .re Recall that is minimized at x", we have
2 f(x") ((v) 2 VS (x - y) +
2 x= - y12
(43)
By integrating the Lipschitz Hessian, similar to inequality Vf + v2 z,) = ff().. Formally,
39
V (1) can be approximated with
1
VV f(g)lle S p0lly 2111..
(44)
Hence, inequality 43 implies that
M
yg) (a* y) +
x y1 2 Flyy 2,l1/110* 2112-
(45)
2
To characterize the terms in the above inequality, we first note that
1: ||r]] 1/ 0.8r: H 3r, + 0,16|| Brel12
$ ||re 2 - 0,64|| Br:112.
For convenience, we denote c _ || | / We have that c E (0, 1] and
y - 21 - (1- 0.64c) (1-0.422)
(46)
We also consider the following vector,
q (V (vf(y) + (8 0.36cM)) 0.6cM 0..6)) =2)) 0.6 (Br++ 0.4MM 0.4cM Br. rr)):
of which the L2 norm is greater than //cl/ 0.6cM p. which can be proved in the eigenbasis of 2 fz)().) By Cauchy's 's inequality, we have that
vf(x") 2 || f<x
0.6cM
(47)
P
Note that x= y (v2f(z))) (vi(x*)- Vf())) The LHS of the above inequality can be
written as (x* - y) (V2 (zz)( a vi(y), where the first term contains V (x* - y). and the second term is bounded as follows.
q V(()) 0.6H,11 (H, r + (B 0.4cM)(re H1 11,
(0.43r: + 0.6 [i, - v²((z)) r.
< -0.11, . 11,1 Pr. 0.4,r.
0.244233|1r.1..
(48)
21

---

On the other hand, observe that inequality can be characterized as follows.
holds for any generic y E R The RHS of inequality
[|Vf(x")) Vf(x")) v)(2))12
1
f||x -2112
2
A||10* 2l12 plx= - y) (y - 2,) + 2 plllys y - 2z
(49)
Therefore, by combining inequalities (45) and 49 we have that
y) y) (B 0.36cM)) rı 2 Vf(y)
(0.5 0.3c) M | y11
0.5pp gy 2: | y/1 0.3c. 1yy - ze
~ - -0:12
2 v fzy)
0.3eM |y - zz 1
(8 - 2.4c)
where the second line is obtained by taking the infimum w.r.t. ||x- 1112.
Then, we apply inequalities
46
48 and ||mll2 I M/p to obtain the following bound.
(x: v) rt 0.24c M(1 (.640))))))
(8-2.44) 2.4 0.3cM (1 -1-00 0.64c²)
B + 0.36cM
Note that the above bound is non-decreasing w.r.t 8, and our construction implies F 2 M. We can substitute in the above inequality with M. Further, note that
(y z1) T, ||rel r1 0.48H, 'r. 2 (1 - 0.4c) ||r:|l2-
We have obtained lower bound of (x* 177-2p zt)) Tt as a function of c. This dependency is removed by taking the infimum, i.e.,
0.24c (1-0.61e))
0.3c (1 (1- - 0.64c²)
(x" - 21) rr
inf cE(0.1]
(8-2.4c)
0.4c
-/eelll.
+ 0.36c
then inequality 42 is obtained.
We this key inequality obtain the following recursion rule.
|| - 2:113 ||xe 2011l1 = 2r, (x* 21) - 1|r 2 0.21|r:
Recall that for F(p, M, Rt). we assumed that ||0*|| 1|2 R. Therefore, for 21 the above recursion implies that the inequality || > M/p can hold for no greater than 5R² p²/ iterations as ||= 1 has be non-negative for any Hence, based on the earlier discussion, we have proved that either ||eele < M/p or V f(z+11 = 0 for all t 2 5R2 p² /M2 and all f F(p, R).
Recall inequality (40), this implies that |/V f (z:)ll2 <
2 for all 5R 12 / + 2p
Remark E.2. Recall the recursion provided by inequality 400 and 4T). The gradients for the
sequence decay couble-exponentiul once they are sufficiently close proves that takes finitely many iterations for the bootstrapping stage of Algorithm 4 to ger arbitrarily close x² in the zero-error case.
Hence, Proposition
E.2 Generalization to the noisy case
Now we prove that, given a bounded number of iterations, the bootstrapping stage in Algorithm provides an 2s that is sufficiently close x with high probability even in the presence of noise. Similar to the zero-error case, we provide the following guarantee.
Theorem E.3. For any fixed p. M and R, the result returned the first stage of Algorithm 4 satisfies
lim sup T T-000 JEFO,,,.R)
E
Vf
(B)
|1
3
T
= 0.
(50)
22

---

(B) denote the realization of vector at the end of the kth iteration in the For convenience, let i
bootstrapping stage and N & [T denote the number of iterations. Therefore, we have Dg = 2x
Further, we define 20 ( - O. We let my, Hy denote the realization of ri, Hm in the +k+ + 1)th (B) = 2 H my As a Benchmark for our analysis, we use H3 to denote the value of Hm- in the zero-error case, i.c., they denotes the (B)
iteration of the bootstrapping stage. Therefore, we have 2++1
(B)
and H 22 (x)( Hence, the update
value of Hm under the special case of m ff 2k
in the zero-error case can be denoted as Tk H f
(B)
We let Eg be the indicator function of the event where there exists an j < such that |
2; (8) ryll2 2 MT-02/p. /p. Intuitively, Es- = describes the event that the optimization steps can be characterized similar to the zero-error case. Notice that Eg is non-decreasing. We have either EN 0, or Ekg 1 for some Kg ... N.. We provide the analysis of Theorem E.. separately for each of these two cases.
For the first case, i.e., when Ey 0, we can follow the earlier arguments and prove the following proposition (see Appendix F33 for details).
(B) (B) Proposition E.4. For any function f E F(p, M, R) and any sequence To Li N-1 R
(B) that satisfies zó = 0 and Ex-1 0, we have ||ra-1lle s 2MT 0.2p when T is sufficiently large.
Recall the definition of En = 0. The above proposition immediately implies that
(B)
11, S 3MMT < M/p x N-
(B)
when T is large. Hence, in such cases, x (B) is obtained by the Newton update. Formally, A denotes the estimator returned by the HessianEst function in the Nthh iteration, we have
(a (B) " A -
(51)
Therefore, by applying the above results to the Lipschitz Hessian condition, have
v v
(B) /
S v [a= + (x (B) (B)
V2
[(x
(B)
2 +
S1a | (B) - x (B)
112
9M2
<
V f( (1_) MN-1 + (x
N
2 f(x 1 - H
2p70.1
3M
9M2
< V fx (<=xx_)) MN-1
+
(B) 42 f(x
N- Å +
(52)
2
070.2
2p70.4
Hence, by direct integration of the tail bounds in Theorem
4.3
we can conclude that
limsup sup E [(
(B) ||
1(Ex = 0) T3 = 0.
(53)
T-o (EF(p.M.R
Now we consider the second case, i.c., when EN = 1. By its definition, we must have the event of (B)
Ex to Ex-1 for unique & E (0, 1, ..., N 1]. which implies that | a (B)
B) 2 >
MT 0.2p....ppp. We prove that conditioned on any of these events, the random variable [[ i++ ll
has a super-polynomial tail, which contributes vanishingly to their moments the asymptotic sense. Formally, let
Mr -
E
V
B 11 1(Ex+1 E, Es = =0]
We aim to prove that
lim sup T-000 ke N-1) (e)(M.
max
sup
Mr NT 0.
(54)
Consider any fixed & E {0, I, N 1} and conditioned on any realization of æ (B) the distribution of 2441 by providing the following proposition, which is proved in Appendix F.4
we characterize
23

---

Proposition E.5. Consider any vectors m. m' E RR, any positive definite matrices H. H' E R with all eigenvalues lower bounded by M, and any fixed parameter Rg N,. Let Hm be the synmetric matrix sharing the same eigenbusis of H but with each eigenvalue X replaced with max {X, m²) ) where m² is chosen to be the smallest value such that ||Hm--mll S Ro- Let H be defined correspondingly for m' and H' We have that
2Ro
H m H m'11
(I m'll2 + Ro 1| H1plp).
(55)
M
Furthermore, when Hm.mm. H ummmmm
O, we have
H (Hm m Hm mmmml
2Ro
3
H m H m (1/m -m'll + Ro R1l - H²(pp) (56)
By choosing Rg = M/P. Hm- HN-1. H' (
mx-1, and m'
[a (-1) ,) for Proposition E.5 the condition of E can be characterized by the estimation errors of the gradient and Hessian. For brevity, we define
v m man-m'm
m'll> 222 + Ro I| 1
We also let 3 denote the minimum eigenvalue of Hyg The condition of Ek41 and Eg 0 implies
that Hm-mm H mnll2 2 7- which implies that v > 342702
aR.7-0.2
according to inequality
(66. Hence, Mg can be bounded as follows.
BRoT 0.2
M E E
2 1
V
3 + 27..2
On the other hand, by generalizing inequality
52
we have
v f((
k+1
(B)
< V fa (B) + (ar
k+1
(B)
2z
(B)
V
2
k
BB)
2
c
k+1
(B)
I
(B)
1
<< V (a (B) mi
BB)
(B)
V2 f
(B)
A
xx++
2
+ [ (./11 (1) - ak
(B)
(il H
2
+
2
0
k++1
BB)
(8)
1
S Roj M
(57)
Therefore,
limsup
sup fe
M₃ N
T
RoM
- 0.2
< lim Sum T-
Vp + Rog +
1
NT
2
270.2
0.
(58)
Since the above bounds are uniform over the index h. equation 54 is implied. The above arguments also show that
limsup sup T T (p)(
P[EN = 1]. N3T3
< limsup
sup T- M,
N max P|ExP|EE+1-1 = 1, Es = 0] N = 0.
(59)
is bounded after entering the Eg = 1 phase. We proceed to bound their contribution to the Nith iteration. To that end, we denote
So far, we have proved that the moments of the gradient norm
V f (B)
G E
(m) M1 1(Ea = =1)]
24

---

This sequence is initialized with Go 0 by definition. We establish the following recursion for sufficiently large T.
1+ w) ) 6N2 (o1i))) PPEN 11 + Ma.
GK+1 S Gik
We note that conditioned on any fixed ziz the gradient norm function approximated with its linear expansion. Formally, let g(z) - v we have
[V((a11)11 1)21 can be
(x ox ()) V2 { (
ff
$ 00
(B) k+11
+ 2
x
k+1
(B)
2x
(B) 2
0(0 (
PR
Then, in the eigenbasis of H, it is clear that
| ||g - f ) + (x - x/ f1|l
[ k+1
mn)
(it - v2 f(ax (i))
+
V2 ((xx( (8) V f= (8) m, f(( (B) ||, Ru H H
Recall that by Theorem 4.3 when T' is sufficiently large, the moments of m, V 18)
Ro
i - (xx
(B)
is upper bounded by any fixed quantity. Therefore, as a rough estimate, we
F
have
(8) |V 21 1(E, 1)} s f (1)) + pRO11 1(Ex 1)
1 N + 6 (p PIE = 1]
Gk 1+
when T is sufficiently large. Consequently, our needed recursion is implied by the monotonicity of Eg, and we have
lim limsup sup T400 JEF(aM.R)
sup
GN T
< sup
sup T-000 Mp
max Mr + 6N2 -PlE, =11) N 1+
1 N
T
(60)
Finally, Theorem
is proved by noting that
E
v (
8
37
E
[
(B)
1(EN 0) T3
GN-
(61)
Hence, equation (50 is implied by equation (53) and inequality (60).
E.3
Proof of Theorem
Proof. Given Theorem our needed inequality (6) is implied by the strong convexity assumption.
Particularly, the implication is due to the fact that f(2)
2 f(x) f for any x E R.d n
2M
Remark E.6. Note that compared to the simple regret guarantee stated inequality (6) we have essentially proved stronger statement that the moments of the gradient at the outcome of the bootstrapping stage follow similar power decay laws. Therefore, while we presented a final stage algorithm that uses non-isotropic sampling to be compatible with general bootstrapping stages, our specific bootstrapping stage actually allows for the use of isotropic (hyperspherical) sampling for gradient estimation in the final stage.
25

---

Proofs of some useful propositions
F.1 Proof of Proposition C.1
Proof. Recall that all 2j have zero expectations. By subgaussianity, we have that all even moments of 2j are bounded follows.
20 =
2eK2t-1p
||,]| 2 KjdK
K=0
20
min
2exp
dk
03
K=0
(1 + In 2)
( = 1, if f = 2, if f 2.
(2 + 2ln 2 In 2)
2)
(62)
2 o
Using AM-GM inequality, the odd moments of 2j can then be bounded using the even moments. Specifically,
E
2F+1
1 E + E 26+2
2s
Therefore, we have obtained the following upper bounds for the comment-generating function.
20
E [exp(szy)]
E
m=
7
1
s2e
< 1
E
2
E [22]
12
2 +
(26)! 2
t=2
Applying inequality 662 the expression above can be bounded with series of (sar))² The coefficient of each (sa,)2 is greater than H. which be verified numerically for e < 2 and inductively for f 2 3. Hence, we have
(sar))2 8!
E [exp(8z;)]
(00,))
(63)
t=
Because zy 's are independent,
1
II [exp(sz;)] S exp 8 Σo9
exp
8
Inequality (66) implied by Markov's bound. Specifically, for any K 0,
P
2j
K
inf E exp
Σ 2j
exp (-sK)
< inf exp e20
$² Σ 03
sK
K2
exp
44, 03
For the same reason, we also have
k²
P
2g S -K
S exp
4 4 o7
26

---

Hence, by union bound.
A
K²
P
24
> j=1
2j 2
K
+
Σ 1=1
2j S -
S exxp
(64)
F.2 Proof of Proposition C.2
Proof. By subexponentiality, the moment-generating function of each |zy] is bounded follows for any
1. 0."
E Elexp(s|2z)) 1+
8 sexp(sK) PP [|zz]]
KjdK
K
S 1 +
8 sexp(sK) min 2exxp
:1
dK
K=0
Jj
2
(65)
30
Because 2y's are independent,
E
exp
8
Σ
< exp
Σ |zsl
II E E[exp(s125))
(66)
I1, 80;))
We choose 8 = 1/(3 E, o,), note that sa $ 1/3, we have (1 - (1-s0,) 2 (3) 35d;
Hence,
1
E
exp
Σ 2j
(In 2 3) =3/23 < 2.
Then, inequality (18) is implied by Markov's bound, i.c.,
P
2j
K
< E
exp
2j
exp (xp(-sk)
K
$ 2 exp
3 03
F.3 Proof of Proposition E.4
To prove the proposition for sufficiently large T, we focus on the regime where N 2 10R²p²/M2+2 We first use proof by contradiction show the existence of hip 10/2 p² /M² such that || l22 < M/p p. Assume the contrary, we have ||ræll2 2 M/p for all k < 10R2 p² 2 Recall we have proved earlier that (see inequality (42))
x -='
Tk 0.6||r
(67)
This assumption implies that R 2 0.6M/p and
x0- - x
( |
|1
> 0.6M/p for all k: < 10
We characterize the evolution of x (B) By Cauchy's inequality and inequality 67
M
(x x
(B) 2
x
x
rk
0.2
x²
b
2
>
0
M
(B)
0.0.
27

---

Note that our assumed lower bound on N implies a lower bound on T. Numerically, one can prove that 7 2 20pR/M. Hence, the above inequality implies that
0.05M
x ox (B))
(I
(B)
(B) ス 0.6||x
x
Ik
(B)
p²
2
Then, by following the proof steps in Proposition F.1
we have that
x=
(B)
x
kx
(B)
-2 x="
xxbb)
(x=00)
(B)
k+1
(B)
Ty
(B)
S ~11.2||mml
+
0.1
x²"
(B)
+
M
(68)
p² R
where the second step is due to the construction of x (B)
(B)
#++1 in Algorithm Recall that
x
D
R. The above inequality implies that if ||r= ||2 2 M/p for all k S 10R2 p²/ D2// then x=* Ty
RR)
non non-increanne -nciicceasing and reaches below at = [10R2 p²/22 //M + 1. However, this contradicts the fact that ||ra la is non-negative, and must conclude the existence of Ko 10R2 p² /2/M2 such that | < M/p.
Now consider any index k with ||rx||2 M/p. By the construction of ru. we have that V -T (²)(xx) Then, by the Lipschitz Hessian condition,
v ff(x==1) - (IN+1 2v rk)) f2
vf(xx) - (xx+1 xk) V f(xx)ll
2
| - 2x112-
(69)
2
Using the strong convexity assumption and triangle inequality, the above bound implies that
P $ - ((mx) (V² 1112 + 2M
- F3 -
| - m2.12
Note that the first term in the bound above is upper bounded by the product of || 2 rullz and the spectral norm of V fxx)) (V convexity, this spectrum norm is further bounded by 1 + Ar || -2all2- Therefore,
fx*++))) By the Lipschitz Hessian condition and strong
(1(2 f( (
< || - F - (1+
M -
P
2M
P
| 2x
(70)
We use inequality (70 bound ||r ll2 recursively. Assume T is sufficiently large such that 0.2 2 20. As rough estimate, we have
M
M
M 0.6 P
2
S 0.6
20p
2p
Recall find kn < 10R2p² 22 such that || 1l2 </pp. By induction, we have ||rx|la V 0.6M/p for all h >> kn- Hence, when k: > ko, inequality (70) implies the following relation, where the RHS is obtained by triangle inequality and the definition of Ex = O.
P |rttill2 <
M pTo.2"
(1+
P M
|1rkll + T0.2
+
P 2M
||
1|2 +
M
P.O.2
Therefore, by induction, have
||ril|2 < M
0.6
2
max
22
TO.2
for any lo > ky + 1, and numerically, ||TN- S 2.2
0.2
/pp
7f > 2kg 6.
28

---

F.4 Proof of Proposition E.5
Proof of inequality (5) We prove the inequality by considering two possible cases. In the first case, we assume that the lg norms of both H m and H' m' are no greater than Ro. In this case, we have Hm- and H m H'. Hence,
1m m 11 '' -1 1
H ((m m') (H' H
(71)
By the fact that all eigenvalues of H are lower bounded by M and the triangle inequality,
|| H m' 1/2 s M-1 (I/m m'lla ||2 + || H =||=||HH"
S M (l|m m'll2 + ||'1
(72)
Then, the needed inequality is obtained by Hmm.m - Hm m'm1 S 2Rg. which follows from the construction of Hm- H' and triangle inequality.
Ro. Without loss of generality, we assume that m² 2 m'*. To be rigorous, here we adopted the convention that m = - if the & norms of H-1m is no greater than Ro. and the same for m accordingly. Based on this assumption, the condition in this case can be simplified as ||/-mm/le Furthermore, we also have yn* M.
For the other case, we have max f11H~>m||l,, (
Ro. and we have that [1 mll2 = Ro-
To prove the needed inequality, we introduce an intermediate variable H' which is defined as the symmetric matrix sharing the eigenbasis of H' but with each eigenvalue Arelaaedd with max X, m m²). Note that Hm- and H' are obtained by projecting H and H' to convex set matrices under the Frobenius norm. We have that
H ||e S
| H|F.
(73)
Therefore, by following the same steps in the first case and noting that all eigenvalues of H are lower bounded by m². we have that
Hm m H ' 11 S m
m']
(l]m m lle + || H1lp Ro).
Compare the above to inequality
(55) it remains to prove that
2Rmm
H m
H m
H m H m
(74)
M
For brevity, we denote that
A H m,
A H 1
A 1 m',
a A M M/m".
In the eigenbasis of H', it clear that
||b ac|l2 s (1 a) ||e||2-
Hence, by Cauchy's inequality, a (b ac) ||a||2 1|6 acl|2 (1 a) ||al| ||c|12-
(75)
Recall that ||c||2 < Ro and this case we have ||all2 = Rg. Therefore, the RHS of the above inequality is upper bounded by (1 a) 122 and we have
(a - c) S (a b) = Ro a bll2
where the first step above is equivalent to inequality 775). and the second step is due to Cauchy's inequality. Finally, it remains to notice that the LHSS of inequality (74) equals ||a cll2. which upper bounded by the LHHS of the above inequality, and its RHS equals the RHS of the above inequality. Hence, inequality (74) is proved.
29

---

Proof of inequality (6). Firstly, if m² = m²" we follow similar arguments from equation
to
inequality (72). Le., this case, we have
Hm (H H m') = (mmmm)) + (HI' Hm mm
(76)
Hence, by triangle inequality and inequality (7).
m (H1 m
1 m )12- < Im - m 122 + || Hm ||F || m 11
S Im m 2|2 + ||'
H|IF Ro.
(77)
Then, for m² m²* define Hm and a, b, in the earlier proof steps. We first prove the following key inequality.
la la-cl22 cl1 | c/l2 s 2/ bl12 11a/12-
(78)
Recall the assumption in this case implies that ||a||2 Ro. By taking the squares both sides, the inequality above equivalent to the following linear inequality of vector a.
(8R b b c) 4R
(Ry + (16 - 1|6 clß (Ro + [|cl1))
(79)
By Cauchy's inequality, the LHS of inequality 79 upper bounded by ||a| |2- 18-18/8 b 2
cl c
The coefficient of ||l|2 in this expression can be further characterized as follows.
| b 2| clβcl12 =4 (4R) | -lll) (4R -0-10 ||b c(blcc12)
+ 16R
|b -cll
1
(4R) (R) [|b1 | |/--cl22 (R) + ||c1))
RO
(4R
(R) (bbb b -cl: (R ||c|
R
+ 16
|bb c cl1
(80)
We prove that the contribution from the second term and the third term in the above expression is non-posionn non-positive. To that end, note that the definition of H H and the assumption of m > m"
imply that (c b) - b 2 O. We have the following inequalities.
c12 + | < ||c|| < RØ-
(81)
Therefore, 0 - 4R (R. - (bb12) - b cl (R | (3)
S
4R ||b - cl and equation (80)
implies that
a. (8R) b - 2| - c) < 4 R + bb - ||b
c (RØ + ||c|()
By utilizing the above bound, inequality 779 proved by noting that RHS is non-negative, which can be proved using inequality (1). As mentioned earlier, this implies inequality 78).
To proceed further, we note that 6 lies the eigenspace of H' associated with eigenvalue m Hence,
H (a c) Hm (a b) + +mn (b c).
Therefore, by triangle inequality, we have
Hn (Hm.. - H m 1l1 <| (a -b]ll2 + m." b|b c/12. Note that by inequality (78) and the fact that all eigenvalues of H are lower bounded by m², we have
(82)
2Ro
m |16 c12 5 ||a c|l2
114m (a (a-b)ll2-
Therefore, it remains upper bound the Eg norm of H'm (a - b). By the definition of vectors a. b.
H (a- -b) = -(m- m') + (H'm. Hm-) a
(83)
30

---

The triangle inequality implies that
Hm (a b)ll2 S m -mmm) m'll2 + Ro [ Hm 11:
(84)
Hence,
2Ro
H (Hm-m H m 112 1+
||a -cl12
(I m 112 + Ro ||lf
Hm l1E)
2Ro
1
|| m H m//1
m
m ||2 + Ro 1 H' 11'ppp
where the last step is due inequality 73 Thus, inequality (56) is implied by the semi-position definiteness of H H'm
Finally, when mn < m'" we let Hm denote the symmetric matrix sharing the same eigenbasis of but with each eigenvalue replaced by max earlier proof steps imply that
(a, (A, m,",". Due to the equivalence H and H', our
2Ro
|| (H H S 1 H m H mm ml 112
([|m m 112 + Ro 11 H H (p)
Hence, by triangle inequality, we can use the above bound follows.
[| (Hm--m m m²) 11 - || [H - -m (Hm H H 1|1
Hm (H m H m 112
< Hm Hm | || H m H m
Hm (H H H
Note that || H m'll2 < 2R. By inequality
773 it is clear that
2Rg
Hm (H m Hm m)) ) 11g s 3 H m H H ml
ml m' m'll, + Ro || H1 11())))
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims are included in our theorem statements.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have included a discussion of constraints of our work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
We have provided the full set of assumptions and a complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

Answer:
[NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.. cc/
pub i gu des Codeeubmies ssion casionoollii icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cc/
wwublic/guideen / //ddideee/Cdeeeeeeee Cooeeeooeeeeeeeeee SudeSuumiiee Swwmisssiiii wsssnooliccyyyyooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
34

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://ttttttsi//p/peee / http:////aaac.a..ccooooooc/////a
Answer: [Yes]
Justification: This paper follows the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theory paper and there is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
35

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperssw hopersswiccoe com/ dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
36

---

Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "0BlIL2nn8Q", "reviewer": "Reviewer_vYTV", "summary": "The paper studies the problem of zero-order optimization of a strongly convex function whose Hessian is Lipschitz continuous. The proposed algorithm exploits zero-order information from the oracle to estimate the Hessian and gradient of the function at each iteration. Using these estimates, the authors employ a second-order method to achieve convergence for the optimization error. The results are asymptotic and valid for a sufficiently large number of function evaluations. The main contribution of the paper is improving the dependency of the achieved optimization error with respect to the dimension. The derived upper bound is minimax optimal with respect to the number of function evaluations, dimension, and the strong convexity parameter.", "questions": "1. As I mentioned earlier, could the authors explain why there is a need for two different gradient estimators?\n\n2. Why does the noise need to be sub-Gaussian? Specifically, the results of Theorem 4.1 also hold for any noise with a finite second moment.\n\n3. Could the authors motivate the second stage of the algorithm? The authors mentioned, \"The role of the final stage is to ensure that $f(x_B) - f(x^*)$ is sufficiently small with high probability,\" but why you need such a guarantee with high probability, and not just in expectation?\n\n4. Could the authors explain why they need a high probability bound in Theorem 4.3 and why expectation bounds are not sufficient?\n\n5. I am a bit confused about where the authors used Assumption A (3). The parameter $R$ does not appear anywhere in the algorithms or in the final bound.\n\n6. It would be helpful if the authors provided a discussion on the number of function evaluations used overall in the main algorithm.\n\n7. A version of Theorem 3.2 has already appeared in [1] without the dependency on $\\rho$. So, the novel aspect of this lower bound is its dependency on $\\rho$, which I found interesting. Please correct me if I'm wrong, but unfortunately, I cannot see the proof of this theorem in the paper.\n\n8. I would like to know the authors' thoughts on higher-order smoothness: if we assume that the higher derivatives are uniformly bounded, do the authors believe it is possible to achieve the dependency of $d$ with respect to the dimension by estimating higher-order derivatives?\n\n9. Could the authors specify the lower bound for $T$ for all the results in the paper to hold?\n\n\n[1] Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Exploiting higher order smoothness in derivative-free optimization and continuous bandits. Advances in Neural Information Processing Systems, 2020.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The result of the paper regarding the upper bound is a significant and surprising contribution. In the literature, there was an optimality gap with respect to the dimension: the existing lower bound was of the order $d$, while the upper bound was of the order $d^{4/3}$. The main anticipation was that the lower bound was not tight enough. However, the result of this paper shows that $d$ is minimax optimal, which I find to be a very valuable observation.", "weaknesses": "The main issue I encountered while reading the paper is that the authors should provide more motivation for their algorithm. For instance, they use two different gradient estimators, GradientEst and BootstrappingEst, but it is unclear why both are necessary and why one is not sufficient. The assumption on the noise is also more restrictive compared to previous work in the literature, see e.g. [1]. The authors assume that the noise is sub-Gaussian, whereas other papers have only assumed a finite second moment. The authors did not explain why this stronger restriction on the noise is needed.\n\nThe main algorithm of the paper, Algorithm 4, consists of two stages. While the first stage of the algorithm seems natural, the second stage is not well motivated.\n\n\n[1] Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Exploiting higher order smoothness in derivative-free optimization and continuous bandits. Advances in Neural Information Processing Systems, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the constructive feedback from the reviewer and have addressed each comment below.\n\n>  Why there is a need for two different gradient estimators?\n \nThe two gradient estimators are tailored to the two phases of our algorithm, which serve distinct purposes. The first stage of our algorithm deals with potential initial conditions with unbounded gradients and highly skewed Hessians. Therefore, we need a gradient estimator whose variance does not depend on the gradient norm to ensure convergence. Thus, we employ the coordinate-wise estimator in BootstrappingEst instead of GradientEst (comparing Theorem 4.1 and 4.3).  \n\nOn the other hand, once the algorithm reaches a point sufficiently close to the global minimum, as specified in equation (6), the hyperellipsoid estimator in GradientEst provides a better bias-variance tradeoff (by a factor of $d$) as the third term on the RHS of inequality (3) becomes dominant. Therefore, in the second stage, we choose this estimator to reduce the estimation error. \n\n>  Why does the noise need to be sub-Gaussian?\n\nWe would first like to emphasize that the sub-Guassian assumption we adopted in this work is merely to simplify the algorithmic design, allowing us to focus on presenting the key ideas for achieving minimax sample complexity. Even with general (non-sub-Guassian) noise distributions that have bounded variance, our results hold by employing more sophisticated mean-estimation methods (e.g., median-of-means instead of naive averaging). Therefore, the adoption of this assumption does not fundamentally weaken our results.\n\nHowever, the sub-Gaussian assumption becomes convenient in our setting compared to prior works, because we completely removed the Lipschitz gradient condition that those works assumed. Specifically, when the Lipschitz gradient condition is assumed, as shown in Akhavan et al. (2020), even simple gradient descent ensures that the squared norm of the updated gradient is linearly bounded by the squared norm of the previous gradient, allowing for a recursion based solely on the second moment of those gradients. Without this assumption, the squared norm of the updated gradient may depend on higher moments of the previous gradient.  This dependency is not immediately removed by Theorem 4.1 as it only states characterization up to the second moment. A sub-Gaussian gradient estimator can provide guarantees for these higher moments.\n\n> Motivate the second stage of the algorithm? Why they need a high probability bound in Theorem 4.3?\n\nPlease refer to the response to the second question. The necessity of a high-probability condition similar to equation (6) in each step is fundamentally required due to the absence of the Lipschitz gradient assumption. \n\nIn fact, we want to highlight that, even in the classical analysis of Newton's method, which assumes zero-error observations, the additional Lipschitz gradient condition was adopted to obtain non-trivial complexity bounds (e.g., see [A], Section 9.5.3), implying the non-trivialness of removing this smoothness condition even for achieving $O(1)$ expected simple regret with unbounded Hessian. We achieve this uniform convergence with a non-trivial modification of Newton’s algorithm. Therefore, we view both stages of our algorithm as main technical contributions.\n\n[A] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.\n\n> where the authors used Assumption A (3)?\n\nThe condition of A3 is not directly used in our algorithm. However, it is required for the regret analysis in the sense that the total number of samples needs to be greater than a function of R for the algorithm to enter the final stage, e.g, see Proposition E.1. This dependency only contributes to an additive term in the total number of samples, and hence does not change the sample complexity asymptotically. \n\n> discussion on the number of function evaluations.\n\nThank you for the feedback. We will add discussions on the sample complexity analysis and show the total number of required function evaluations is indeed no greater than $T$. \n\n> Theorem 3.2 vs the lower bound in [1]?\n\nDue to space constraints, we have provided the proof of Theorem 3.2 in Appendix B. While we use different smoothness assumptions than those in [1], our lower bound can be considered a strengthened version of Theorem 6.1 in [1] under $\\beta=3$, as discussed in Appendix A.\n\n> higher-order smoothness?\n\nWe share the belief that under higher-order smoothness conditions, it is possible to achieve the corresponding optimal sample complexity with estimators of higher-order derivatives. \n\n> lower bound for 𝑇 for all the results in the paper to hold?\n\nFor all our analysis, the required lower bound of $T$ are polynomials of $R$, $\\rho$, $M$, and $d$, e.g., see the requirement in Proposition E.1. However, as the focus of this work is on the asymptotic analysis, we did not optimize our algorithm or analysis for these non-asymptotic requirements.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "75YWR559S5", "reviewer": "Reviewer_QNuA", "summary": "This work studies the convergence of zeroth order stochastic optimization for a class of strongly convex, second-order smooth objective functions.  The authors assume that the noisy one-point feedback oracle is available, and the additive noise is subgaussian. Both the asymptotic upper bound and the matching lower bound for the minimax simple regret are provided.", "questions": "1. Remark 4.2: I cannot understand the first sentence. Are there any established results for the case of the cubic polynomial function $f$?\n2. Algorithm 4: Is the $\\hat H$  returned by HessianEst invertible?\n3. Proof of Theorem 3.1: \n1)  In line 200, \"First, recall our construction ensures that,\" could the author provide the proof of this statement? 2) In lines 203-204, the two displays omit the dimension dependence. Will this omission impact the final dimension dependence?\n4. Line 358: I cannot see how to apply Lemma B.2, also known as Proposition 7 in [Yu et. al. 2023]. What is the $Var_{f\\sim p}[f(x)]$?", "limitations": "The paper proposes a new algorithm but does not provide any numerical results to validate it. There are many interesting questions that could be investigated numerically regarding this method, such as its dependence on the length of the first and second stages.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors propose a novel algorithm that combines gradient estimation, bootstrapping procedures, and a mirror descent procedure. This combination enables accurate estimation of gradients and Hessians under second-order smoothness, thereby achieving the optimal rate.", "weaknesses": "The idea of this work is interesting, but the presentation needs improvement. Some main results should be explicitly and rigorously stated as theorems, for example, eq (6). Additionally, it is unclear why the two stages in Algorithm 4 are necessary. Providing intuition and explanation for the two stages and the choice of parameters in Algorithm 4 would be beneficial.\n\nFurthermore, the proof of the upper bounds contains gaps. The result obtained in line 601 is $\\lim_{T\\to\\infty} T^{2/3}E[\\|\\nabla f(x_N^B)\\|^3]=0$. It is unclear how $M$ and $\\rho$ enter the final result and match eq(6) with the specific choice of $\\epsilon$ in line 170. More detailed steps in the proof would help clarify this connection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the constructive feedback from the reviewer and will state equation (6) formally as a Theorem. Below are the point-to-point responses to the comments.\n\n>Necessity of the two-stage algorithm\n\n  The two phases of our algorithm are designed to handle distinct challenges. The first stage of our algorithm deals with potential initial conditions with unbounded gradients and highly skewed Hessians. To that end, we need a gradient estimator whose variance does not depend on the gradient norm to ensure the uniform boundedness of $E[f(x_B)-f^*]$. Therefore, we employ the coordinate-wise estimator in BootstrappingEst for gradient estimation in the first stage.\n\nIn fact, the bootstrapping stage requires a non-trivial modification of the Newton step to achieve the uniform convergence guarantee of $E[f(x_B)-f^*]=O(1)$ (see Algorithm 4) without relying on the Lipschitz gradient condition assumed in prior works. We want to emphasize that even in the classical analysis of Newton's method, which assumes zero-error observations, the additional Lipschitz gradient condition is used to obtain non-trivial complexity bounds (e.g., see [1], Section 9.5.3). This highlights the difficulty of removing this smoothness condition, and we view the removal of this assumption in our work as one of the main technical contributions.\n\n[1] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.\n\nThe second stage of our algorithm is needed to finetune the result from the first stage to achieve the optimal sample complexity. Once the algorithm reaches a point sufficiently close to the global minimum, as specified in equation (6), the hyperellipsoid estimator in GradientEst provides a better bias-variance tradeoff (by a factor of $d$) as the third term on the RHS of inequality (3) becomes dominant. Using this alternative estimator in the second stage allows us to reduce the estimation error by a factor of $d^{2/3}$. \n\n> gap from line 601 to equation (6)\n\nThanks for pointing this out. This step is due to the strong convexity condition, which implies that $\\frac{||\\nabla f(x)||_2^2}{2M} \\geq f(x)-f^*$ for any $x\\in\\mathbb{R}^d$. Recall that in our main theorems we are considering the limits as $T\\rightarrow +\\infty$ for fixed $d$, $M$, $ \\rho$, and $R$ (this will also be stated in the updated version of the theorem for equation (6)). The convergence in inequality (6) is obtained by simply plugging in the definition of $\\epsilon$ and the inequality above obtained from strong convexity into the limit of $ 𝑇^{2/3} 𝐸[||∇𝑓(𝑥_𝑁^{(𝐵)})||_2^3]$. \n\n>The first sharpness statement in Remark 4.2?\n\nThis claim states that for any fixed $\\lambda_z$, $\\rho$, and $d$, there exists a function $f$ in $\\mathcal{F}(M,\\rho,R)$ and a matrix $Z=\\lambda_z I$ such that the bias of GradientEst is exactly given by inequality (2). One such example of $f$ can be constructed as a function that is locally a polynomial of degree $3$, with its cubit term given by $f(\\boldsymbol{x} )=\\frac{\\rho}{6}\\sum_{k}(x_k^3)$, where $x_k$ are the individual coordinates of $\\boldsymbol{x}$. While this construction of $f$ is elementary, the bias of GradientEst over this function is derived from integration over the hypersphere, which is standard and well-established.   \n\n>Is the $\\hat{H}$ returned by HessianEst invertible?\n\nNote that at the end of this subroutine, we raised all eigenvalues of \\hat{H} to at least M. Hence, the returned $\\hat{H}$ is positive definite, which must be invertible. \n\n>Proof of Theorem 3.1: In line 200?\n\nThe condition $||x_T-x_B||_2\\leq M/\\rho$ is guaranteed by the clipping step in the final stage in Algorithm 4, where we project $r$ to the $L_2$ ball of radius $\\frac{M}{\\rho}$, and $x_T$ is created with $x_B+r$.  \n\n>In lines 203-204\n\nSimilar to what we have clarified in the comment above for equation (6), we shall clarify that the notation $f=o(g)$ means that  $\\lim_{T\\rightarrow +\\infty} f/g=0$ for any fixed $M$, $\\rho$, $R$, and $d$. This property is independent of any multiplicative factor of $d$, and it does not impact the asymptotic result for $T$ being sufficiently large.\n\n> Line 358: how to apply Lemma B.2, and what is the 𝑉𝑎𝑟𝑓∼𝑝[𝑓(𝑥)]?\n\nWe choose $p$ to be the uniform distribution over the function class $\\{f_1,f_2\\}$, as stated in line 347, so that each $f_k$ has a probability of $½$. To apply Lemma B.2, we verify that the condition of uniform sampling error in Lemma B.2 is satisfied, which is shown in lines 361-368. The $\\textup{𝑉𝑎𝑟}_{f\\sim p}[𝑓(x)]$ under this prior is simply $(\\frac{f_1(x)-f_2(x)}{2})^2$, and it is upper bounded by $\\pi^2 y_0^2$ as mentioned in line 346-347.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "7Tbqluy1Ch", "reviewer": "Reviewer_X3iq", "summary": "The paper studies zero order stochastic optimization (the learner has access to noisy function evaluation only) assuming the objective is $M$-strongly convex and has a $\\rho$-Lipschitz (in forbenius norm) Hessian. Matching upper and lower bounds are presented, which establish a tight result of suboptimality $\\Theta(d T^{-2/3}M^{-1})$ (w.h.p.) after $T$ function evaluations.", "questions": "- Lines 125-126: 1-subgaussianity already implies variance $\\leq 1$.\n- Akhavan et al. (2020) consider the Lipschitz gradient setting and do not require a Lipschitz Hessian. Hence it seems their results and yours are incomparable (correct?). Given this I did not understand lines 315-317: \"On the other hand ... well.\" Do you include Akhavan et al in this statement? It doesn't seem true that a direct application of your algorithm order wise improves the result of Akhavan et al because your result does not apply in their setting.\n- Since we consider a twice differentiable objective over a bounded domain, it follows the gradient is in fact Lipschitz. With this in mind, are the assumptions of Novitskii & Gasnikov (2021) indeed stronger than those made in this work?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* A tight result is achieved for the setting studied.\n* On the technical side, the gradient evaluation procedure in the final stage of the algorithm uses samples from the ellipsoid induced by the Hessian approximation rather than opting for isotropic sampling. Further, a novel approach for analyzing the bias and variance of this estimation procedure is presented that yields sharp bounds. This technique has not been used by prior works, and seems crucial for the minimax optimal result.\n* This result improves over the most closely related prior state-of-the-art Novitskii & Gasnikov (2021) by a factor of $d^{1/3}$, who require an additional Lipschitz gradient assumption (see discussion in Appendix A).", "weaknesses": "Nothing in particular.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the constructive feedback from the reviewer. Below are the point-to-point responses to the comments.\n\n>Implication of bounded variance from 1-subgaussianity\n\nWe would like to clarify that our intention in mentioning both assumptions was to use the sub-Gaussian assumption to simplify the algorithmic design and meanwhile explicitly state the bounded variance condition for readers who may not be familiar with the properties of sub-Gaussian variables.\n\nHowever, we want to emphasize that, of the two assumptions, the bounded variance condition is more fundamental to our results. The sub-Gaussian assumption can be removed by employing more sophisticated mean-estimation methods, such as median-of-means instead of naive averaging. In the revised manuscript, we will clarify that the use of the stronger sub-Gaussian assumption is for simplicity. We will also refer to references related to these alternative mean estimators, e.g., [1].\n\n\n[1] A. Nemirovskii and D. Yuom. Problem Complexity and Method Efficiency in Optimization,\". Wiley, 1983.\n\n> Applicability of our result to Akhavan et al. (2020) and the comparison in line 315-317\n\nAs mentioned in Appendix A of our paper, although Akhavan et al. (2020) did not directly assume a Lipschitz Hessian, our result can be related to their $\\beta=3$ smoothness condition (which we refer to as the $k=3$ smoothness condition in our paper). The bound we discuss in lines 315-317 corresponds to Lemma 2.3 in Akhavan et al. (2020). As a sanity check, the prior work needed to assume this higher-order smoothness condition to obtain a bound that scales with $r^2$ for the gradient estimator. This is because, with only the Lipschitz gradient condition, the best achievable bound scales with $r$, which is worse by a factor of $1/r$.\n\n\n> Is Lipschitz gradient over bound domain in Novitskii & Gasnikov (2021) indeed a stronger assumption?\n\nWe would like to clarify that although the twice differentiability implies the finiteness of the second-order derivatives over a compact set, it does not imply that the gradient is Lipschitz with a fixed constant such as $\\rho$ or $L$ even for a fixed compact set. In other words, the Hessian can be finite but unbounded. A simple example is that the function class of all quadratic polynomials (with arbitrarily large second-order derivatives) satisfies  Lipschitz Hessian but not Lipschitz Gradient. Therefore, the Lipschitz gradient condition has to be explicitly assumed in prior works in addition to the higher-order smoothness conditions. \n\nNotably, even in the classical analysis of Newton's method, which assumes zero-error observations, an additional constant factor associated with the Lipschitz gradient condition is used to obtain non-trivial complexity bounds (e.g., see [2], Section 9.5.3). This demonstrates the difficulty of removing this smoothness condition. We introduced a non-trivial modification of the Newton step in the bootstrapping stage to achieve a uniform convergence guarantee of $E[f(x_B)-f^*]=O(1)$ (see Algorithm 4), which removes the need for the Lipschitz gradient condition. We consider this to be one of our main technical contributions. \n\n[2] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "8RP3bviyQN", "reviewer": "Reviewer_cqSV", "summary": "The paper consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. Authors provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds. They propose an algorithm that features a combination of a bootstrapping stage and a mirror-descent stage.", "questions": "I have a few questions and suggestions:\n\n- It seems that Theorem 3.1 can be improved in terms of dependence on the problem dimension $d$ using tricks from the work of _Akhavan et al. (2023)_ [1]\n\n- Can the authors explain what the final result would look like if $w_t$ does not necessarily have zero mean, but is independent of vector $e$ (randomization on the sphere)? Also, if we consider deterministic noise $|\\delta(x)| \\leq \\Delta$ as noise. \n\n[1] Akhavan A. et al. (2023). Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm //arXiv preprint arXiv:2306.02159.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The authors consider a problem formulation where the gradient of the function or higher order derivatives are not available. This problem formulation is of extreme interest in the field of Machine Learning. However, the work has many weaknesses (see below).", "weaknesses": "1. Almost no mention is made of work motivation. This is an important part that **cannot be missed**...\n\n\n\n\n2. Also, this paper gives the impression that **it was produced clearly not in this year**, since the main references are **from 2021** and earlier. But since 2021, the research, in particular in the area of zero-order optimization has a lot of interest in the community and is highly advanced compared to what the authors cited as related works. For example, in addition to a number of cited papers studying the zero-order optimization problem with the assumption of increased smoothness of the function, there is already a more recent paper that has been missed: _Akhavan et al. (2023)_ [1], which proposes an improved analysis of gradient approximation bias estimation as well as second moment estimation. Similarly, there is a weakly described section presenting different gradient approximations, where the main focus fell on the smoothing vector (Gaussian vector or Randomized vector). But, there are already a number of papers, such as _Gasnikov et al. (2024)_ [2], which have shown that the randomized approximation clearly performs better on practical experiments than the Gaussian approximation. It seems better to give an overview of different gradient approximations, including $l_1$ randomization, in this section\n\n\n3. Since I have already mentioned the topic of practical experiments, it is important to note that despite the fact that the authors provide mainly theoretical work, a paper that is intended for presentation at the NeurIPS conference should **show the effectiveness of the proposed results** in real life. This paper lacks any experiments, which is a major weakness of the paper.\n\n4. The structure of the article is poorly chosen... It seems that the sections \"Main contribution\", \"Discussion\" and \"Conclusion\" would **have improved the presentation** of the article's results.\n\n5. Regarding the results themselves, essentially **only one result is presented**, which is a minor contribution. It would be interesting to consider when the function is not only twice differentiable but also has a higher order of smoothness, as well as other settings of the problem: convex, non-convex, maybe the Polyak–Lojasiewicz condition, etc.\n\n[1] Akhavan A. et al. (2023). Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm //arXiv preprint arXiv:2306.02159.\n\n[2] Gasnikov, A. et al. (2024). Highly smooth zeroth-order methods for solving optimization problems under the PL condition. Computational Mathematics and Mathematical Physics.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Please find our responses below.\n\n> Almost no mention is made of work motivation. \n\n- The importance of stochastic optimization is clearly mentioned in our introduction. \n\n- The motivation for this work stems from a lack of understanding of the sample complexity under convexity and higher-order smoothness. As stated in Lines 39-46 and summarized in Table 1, the problem of finding tighter complexity bounds for higher-order smooth functions has been widely studied, but the existing sample complexity bounds all have an apparent gap in the regime of $k \\geq 2$. \n\n> Also, this paper gives the impression that it was produced clearly not in this year, since the main references are from 2021 and earlier.\n\n- We have cited papers from beyond 2021, such as Lattimore & György (2023) and Yu et al. (2023). \n\n- Thank you for your suggestion on references. However, the references you mentioned, Akhavan et al. (2023) and Gasnikov et al. (2024), address different research questions from those in our paper. They focus on zeroth-order optimization under assumptions such as the PL condition and higher-order Hölder smoothness. In contrast, we assume strong convexity and a Lipschitz Hessian. More specifically, similar to other related works, Akhavan et al. (2023) adopt the additional assumption of the Lipschitz gradient while we do not impose this condition. Their $O(r^2)$ bound on the bias of the $L_2$ gradient estimator for $\\beta=3$ is implied and strengthened by our bound in Theorem 4.1 as we discussed in Appendix A. On the other hand, Gasnikov et al. (2024) focus on adversarial bandit problems with (almost) adversarial noises, whereas we consider stochastic bandit problems with i.i.d. random noises.\n\n\n> … a paper that is intended for presentation at the NeurIPS conference should show the effectiveness of the proposed results in real life. This paper lacks any experiments, which is a major weakness of the paper.\n\n- Our work addresses the theoretical question of bandit optimization under strong convexity and Lipschitz Hessian. We provide matching lower and upper bounds for simple regret, thereby fully resolving the complexity of this fundamental problem. Given the theoretical nature of our contributions, experimental validation is outside the scope of this study.\n\n> It seems that Theorem 3.1 can be improved in terms of dependence on the problem dimension d using tricks from the work of Akhavan et al. (2023)\n\n- Under the current problem setting, the tricks from Akhavan et al. (2023) cannot improve the dependence on $d$ in Theorem 3.1. This is because our lower bound in Theorem 3.2 already matches Theorem 3.1 in its dependence on $d$.  \nFurthermore, the dependence on $d$ in Akhavan et al. (2023) is suboptimal compared to our bound. Specifically, their rate is $d^{2 - \\frac{2}{\\beta}}$ (where $\\beta \\geq 1$ is the order of Hölder smoothness), while our rate is linear in $d$. Therefore, we believe that applying techniques from Akhavan et al. (2023) is unlikely to improve the dependence on $d$.\n\n> Can the authors explain what the final result would look like if 𝑤𝑡 does not necessarily have zero mean, but is independent of vector 𝑒 (randomization on the sphere)? Also, if we consider deterministic noise |𝛿(𝑥)|≤Δ as noise.\n\n- Thank you for pointing out this interesting future direction. In our work, we consider the stochastic bandit setting where the noises are i.i.d. random variables. If $w_t$’s are dependent on $e$ or are deterministic, the problem would fall into the category of adversarial bandits, which requires fundamentally different approaches and is outside the scope of our paper.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper addresses zero-order optimization of a strongly convex function with a Lipschitz continuous Hessian, proposing an algorithm that uses zero-order information to estimate the Hessian and gradient, enabling a second-order method to achieve minimax-optimal convergence for the optimization error, particularly improving the error's dependency on the dimension. 

There was some initial concerns on the presentation of the paper, but these were offset by the strength of the results. The reviewers agree that the paper's contribution in bridging the optimality gap is significant. It corrects the current conjecture in the community that the optimal rate should be of the order $(d^2/T)^{2/3}$, as proposed by Akhavan et al. (2023). The idea of estimating the Hessian using zero-order information and employing a Newton-type method within this framework is novel and smart.

The authors are advised to revise the paper carefully to address the following three points:
* The paper could be significantly better written in terms of the motivations and intuitions behind the algorithms.
* The sub-Gaussian assumption is unnecessary, and the independence assumption is sufficient.
* The literature review is outdated.
Decision: Accept (poster)