On the Almost Sure Convergence of the Stochastic Three Points Algorithm
Authors: Taha EL BAKKALI EL KADI
Omar Saadi
Venue: ICLR 2025 Poster (2025)
Keywords: Derivative-free optimization
Zeroth Order optimization
Almost sure convergence
Stochastic Three Points Algorithm.
Primary area: optimization

Abstract: The stochastic three points (STP) algorithm is a derivative-free optimization technique designed for unconstrained optimization problems in $\mathbb{R}^d$. In this paper, we analyze this algorithm for three classes of functions: smooth functions that may lack convexity, smooth convex functions, and smooth functions that are strongly convex. Our work provides the first almost sure convergence results of the STP algorithm, alongside some convergence results in expectation.
For the class of smooth functions, we establish that the best gradient iterate of the STP algorithm converges almost surely to zero at a rate of $o(1/{T^{\frac{1}{2}-\epsilon}})$ for any $\epsilon\in (0,\frac{1}{2})$, where $T$ is the number of iterations. Furthermore, within the same class of functions, we establish both almost sure convergence and convergence in expectation of the final gradient iterate towards zero.
For the class of smooth convex functions, we establish that $f(\theta^T)$ converges to $\inf_{\theta \in \mathbb{R}^d} f(\theta)$ almost surely at a rate of $o(1/{T^{1-\epsilon}})$ for any $\epsilon\in (0,1)$, and in expectation at a rate of $O(\frac{d}{T})$ where $d$ is the dimension of the space.
Finally, for the class of smooth functions that are strongly convex, we establish that when step sizes are obtained by approximating the directional derivatives of the function, $f(\theta^T)$ converges to $\inf_{\theta \in \mathbb{R}^d} f(\theta)$ in expectation at a rate of $O((1-\frac{\mu}{2\pi dL})^T)$, and almost surely at a rate of $o((1-s\frac{\mu}{2\pi dL})^T)$ for any $s\in (0,1)$,  where $\mu$ and $L$
are  the strong convexity and smoothness parameters of the function.

Published as a conference paper at ICLR 2025
ON THE ALMOST SURE CONVERGENCE OF THE STOCHASTIC THREE POINTS ALGORITHM
Taha EL BAKKALI EL KADI, Omar SAADI UM6P College of Computing
Benguerir, Morocco
(taha e baakkali, i, omar. saadi 8 @ummp.m ma
ABSTRACT
The stochastic three points (STP) algorithm is derivative-free optimization tech- nique designed for unconstrained optimization problems in Rdd this paper, we analyze this algorithm for three classes of functions: smooth functions that may lack convexity, smooth convex functions, and smooth functions that are strongly convex. Our work provides the first almost sure convergence results of the STP algorithm, alongside some convergence results in expectation. For the class of smooth functions, we establish that the best gradient iterate of the STP algorithm converges almost surely to zero at rate of o(1/T / -)) for any (0, z). where T is the number of iterations. Furthermore, within the same class of functions, we establish both almost sure convergence and convergence expectation gradient iterate towards zero. For the class of smooth convex functions, lish that f(²)) converges to inføgR f()) almost surely at a rate of o(1/T)=( for any e E (0. 1), and in expectation at a rate of O 4 where d is the dimension of the space. Finally, for the class of smooth functions that strongly convex, we establish that when step sizes are obtained by approximating the directional derivatives of the function, f(0") converges inføeR f(0) in expectation at a rate of O((1 z ) and almost surely at a rate of o((1 ) for any s (0, 1), where μ and are the strong convexity and smoothness parameters of the function.
the final estab-
INTRODUCTION
We are interested in the minimization of smooth function f fd R:
min f()),
BE
where we work within the constraint of not having access to the derivatives of f. relying exclusively a function evaluation oracle. The methods used in this framework called derivative-free meth- ods or zeroth-order methods (Conn et al., 2009; Ghadimi & Lan, 2013; Nesterov & Spokoiny, 2017; Larson al., 2019; Golovin et al., 2020; Bergou et al., 2020). They are increasingly embraced for solving many machine learning problems where obtaining gradient information is either impractical or computationally expensive, remaining crucial in applications such as generating adversarial tacks on deep neural network classifiers (Chen et al., 2017; Tu et al., 2019), reinforcement learning (Malik al., 2019; Salimans et al., 2017), and hyperparameter tuning of ML models (Snock al., 2012; Turner et al., 2021). Therefore, exploring the theoretical properties of derivative-fres methods not only of theoretical interest but also crucial for practical applications.
Zeroth-order optimization methods can be divided into two main categories: direct search methods and gradient estimation methods. In direct search methods, the objective function evaluated along set of directions to guarantee descent by taking appropriate small step sizes. These directions can be either deterministic (Vicente, 2013) or stochastic (Golovin et al., 2020; Bergou et al., 2020). In contrast, gradient estimation methods approximate the gradient of the objective function using geroth-order information to design approximate gradient methods (Nesterov & Spokoiny. 2017; Shamir, 2017).

---

Published as a conference paper at ICLR 2025
A recent and noteworthy zeroth-order method is the Stochastic Three Points (STP) algorithm (see Algorithm 1). directed search method with stochastic search directions, introduced by Bergou et al. (2020). The STP algorithm stands out among zeroth-order methods for its balance of simplicity and strong theoretical guarantees.
Algorithm Stochastic Three Points (STP)
1: Input: 0¹ R step size sequence farh21 (0, oo))) probability distribution D on R..
2: for I.= /= ... do
3: Generate random vector 8 DD
4: gi+1 = arg minge (00 (t- f(0).
5: end for
Compared to deterministic directed search (DDS) methods, the worst-case complexity bounds for STP are similar, however, they differ in their dependence on the problem's dimensionality. For STP, the bounds increase linearly with the dimension (Bergou et al., 2020). whereas for DDS, they increase quadratically (Konečný& & Richtárik, 2014; Vicente, 2013). Specifically, when the objective function is smooth, STP requires Odd function evaluations to get a gradient with norm smaller than in expectation. For smooth, convex functions with minimum and a bounded sublevel set, the complexity is (dde-) to find an e-optimal solution. In the strongly convex case, this complexity reduces further to O(d log In all these cases, DDS methods exhibit analogous complexity bounds but with a quadratic dependence on d. i.e., de instead of d. In comparison to directed search with stochastic directions, STP also matches the complexity bound derived by Gratton et al. (Gratton et al., 2015) for the smooth case, which is the only case they address in their work. In their approach, decrease condition is imposed to determine whether to accept or reject step based on a set of random directions. The Gradientless Descent (GID) algorithm (Golovin et al., 2020) another direct search method with stochastic directions. Golovin et al. show that an e-optimal solution can be found in O log(d) log [RE- (RE-)) ) for any monotone transform of a smooth and strongly convex function with latent dimension < d, where the input dimension is d, R is the diameter of the input space, and Q is the condition number. When the monotone transformation is the identity and d, this complexity higher than the one obtained for the STP algorithm by factor of log(d). However, it is important to note that monotone transforms of smooth and strongly convex functions are not necessarily strongly convex.
Compared to approximate gradient methods, STP matches the complexity bounds of the random gradient-free (RGF) algorithm (Nesterov & Spokoiny, 2017) (see section 6) across the three cases: smooth non-convex, smooth convex, and smooth strongly convex. This matching in complexities is in terms of the accuracy c and the dimensionality
In practical terms. for classical applications of zeroth-order methods, STP variants demonstrate strong performance when compared to state-of-the-ar methods. For instance, in reinforeement learning and continuous control, specifically in the MuloCo simulation suite (Todorov al., 2012), STP with momentum (which, in expectation, achieves the same complexity bounds as standard STP, see Gorbunov et al. (2020)) outperforms methods like Augmented Random Search (ARS), Trust Re- gion Policy Optimization (TRPO), and Natural Policy Gradient (NG) across env environments such as Swimmer-vi I, Hopper-v1, HalfCheetah-vl, and Ant-v1, Even in the more challenging Humanoid-vl environment, STP with momentum achieves competitive results (Gorbunov et al., 2020). Addition- ally, in the context of generating adversarial attacks on deep neural network classifiers, the Minibatch Stochastic Three Points (MiSTP) method (Boucherouite et al., 2024) demonstrates superior perfor- mance compared to other variants of zero-order methods, that are adapted to the stochastic setting, such RSGF (also called ZO-SGD) (Ghadimi & Lan, 2013), ZO-SVRG-Ave and ZO-SVRG (Liu et al., 2018).
Within the realm of first-order optimization methods that rely gradient information, numerous studies have investigated the almost sure convergence of the Stochastic Gradient Descent (SGD) algorithm and its variants (Bertsekas & Tsitsiklis, 2000; Nguyen et al., 2019; Mertikopoulos et al., 2020: Sebbouh et al., 2021; Liu & Yuan, 2022). In contrast, the literature on the almost sure conver- gence of zeroth-order methods remains less developed compared to that of SGD.
2

---

Published as a conference paper at ICLR 2025
In (Gratton et al., 2015), the authors investigate zeroth-order derect-search methods under prob- abilistic descent framework. Specifically, they generate randomly the search directions, while as- suming that with certain probability at least one of them is of descent type. For smooth objective functions, their analysis establishes (in Theorem 3.4) the almost sure convergence of the best iterate of the gradient norm to zero. However, the analysis does not provide convergence rate for this almost sure convergence result, nor does it guarantee the convergence of the gradient norm of the last iterate. In our paper, we provide such results for the STP algorithm (see Table 1). (Gratton et al., 2015) also establish (in Corollary 4.7) a convergence rate ((1/VT) for the best iterate with overwhelmingly high probability, but this rate is still not guaranteed almost surely. In our work, we provide the first almost sure convergence rate of the best iterate for zeroth-order methods (see Ta- ble 1). More recently, Wang & Feng (2022) explore the convergence of the Stochastic Zeroth-order Gradient Descent (SZGD) algorithm for objective functions satisfying the ł.jjaiiewizz. inequality. Assuming smoothness, they demonstrated (in Lemma 1) that the gradient norm of the last iterate converges to zero. Furthermore, in Lemma 2, they proved that the sequence generated by the SZGD algorithm converges almost surely to critical point, which is a stronger result, since the gradient of f is continuous. However, this analysis is limited to Lojasiewicz functions, which, by definition, satisfy strong property which is the property essentially used in the analysis of strongly convex functions.
In this paper, are interested in studying the almost sure convergence of the STP algorithm. For the three classes of functions (smooth, smooth convex, and smooth strongly convex), first convergence results, in terms of expectation, were provided in Bergou et al. (2020). However, is crucial to note that ensuring almost sure convergence properties is essential for understanding the behavior of each trajectory of the STP algorithm and guaranteeing that any instantiation of the algorithm converges with probability one.
Our Contribution & Related Work. In cases where the only verified assumptions regarding the function are its smoothness and having a lower bound, Bergou et al. established in their paper (Bergou et al., 2020, Theorem 4. that by using Algorithm and selecting step size sequence Vi h22 with a > O, the best gradient iterate converges in expectation to 0 at a rate of O vd ). Expanding on this, we prove that employing a similar step size sequence { (1T+. Ja21 with e E (0, }
{ a.
/T
results in an almost sure convergence rate of o( - which is arbitrarily close to the rate achieved for the convergence in expectation when e close to (see Theorem 1). It's worth noting that a sim- ilar almost sure convergence result has been established for the SGD Algorithm. For more informa- tion, refer to (Sebbouh et al., 2021, Corollary 18) and (Liu & Yuan, 2022, Theorem 1). However, it should be noted that this similar result for the SGD Algorithm is provided for mingges || / ((')) while for the STP Algorithm, it is provided for minisegrl V (( More precisely, for the STP algorithm, we have minl Iaceess/////CC (00) = o(1/T3-9), while for the SGD algorithm, we have min || V f(0) o by Bergou et al. (Bergou et al., 2020, Theorem 4.1) about the convergence in expectation or our first result about the almost sure convergence, is that they don't 't guarantee the gradient of f at the final point 6T to be small (either in expectation or almost surely). Instead, they assure that the gradient of f at some point produced by the STP algorithm is small. In our paper, we additionally prove that the gradient of ʃ at the final point 0" converges to 0 almost surely and in expectation without re- quiring additional assumptions about the function beyond its smoothness and having a lower bound (see Theorems 2 and 3). Notably, for the case of the SGD algorithm, the question of the almost sure convergence of the last gradient itcrate has been addressed in Bertsekas & Tsitsiklis (2000).
The issue with both convergence results, whether it's the one
For smooth convex functions, if f has global minimum 0* and possesses a bounded sublevel set, we show that selecting a step size sequence ag = ( for some B E (0. 1) ensures that f(0T) converges almost surely to f(0)) at rate of of o( ) for all e E (23, 1) (see Theorem 5). A similar result, with the same convergence rate and the same criteria for choosing the step size sequence, is established for the stochastic Nesterov's 's accelerated gradient algorithm by Jun Liu et al. in (Liu & Yuan, 2022, Theorem 3). For the same class of functions and under the same assumptions, Bergou et al. established in (Bergou et al., 2020, Theorem 5.5) that for a fixed precision and a sufficiently large number of iterations T on the order of !. by selecting a step size sequence
|100 thee)= f(0')) J:21 where sufficiently small on the order of EI)( - [(0),, one can LA
3

---

Published as a conference paper at ICLR 2025
get: B[ S c. Here, the choice of h depends on the quantity [0T which is not known at the begining. Moreover, the theorem does not guarantee that Ef ) converges to f(0)), because the step sizes depend on In contrast, in Theorem 4, we show that by selecting step size sequence { he21, where a is suitably chosen, [R[ [f(((")) converges to f(0)) at a rate of (1
For smooth, strongly convex functions, Bergou et al. established in (Bergou al., 2020, Theorem 6.3) that, for any 6 > 0, using the step size sequence { (1i(0"+hhs)) +hsx)= 1121, where h is small on the order of ve, the gap between the expected value of the objective function and its infimum stays
Lh
within accuracy for number of iterations on the order of log( /(0')=iuloced /(0)
However, this result doesn't 't indicate how the gap [[ -inffeRd f(0) improves with more iterations and does not guarantee convergence since the step sizes depend on c. To address this issue, we define the step size sequence as { [ Lh -====((0']] J21 with a suitable h, leading to a convergence rate of (((1 - 2rdz )²) in expectation, and ((11 8 2gdL )²) surely for all (0, 1) (see Theorems 6 and 7). All of our convergence rates are succinctly presented in Table 1.
Table I: Summary of convergence rates for the STP algorithm.
Ascump
Step
13,5
8 h2zi.a20
min V SO0))l
8/O
Thm 4.1
Rergon (2020)
Smooth
1356
min /(0')) 12
Thm
E (0, }
(edrz
15,6
D of <0
[v
(1)
Thm
Ei de
Smooth. conves
1,233,66
0y 4: a suitebly chosen
[(6") - (100))
e/0(4)
Thm
/o (i-e))
1,23,66
Oe = (1-2).
s(6") - f(07)
Thm
Ve (28.1)
Smooth, stungly DOIVET
1,3.6677
[1100 [=00*+ ((00))
Lh
1021
s(6") f(0))
k/O((1 2)²)
Thm
is bego enough
14566677
110
1221
T(6 1(A")
us. /o((1 8)*)
Thm
I is luge enough
8 21 (0, 1)
PROBLEM SETUP AND ASSUMPTIONS
We interested in the following optimization problem:
min f()), DE
where the objective function f ; Rd + IR is differentiable and bounded from below. In this context, work within the constraint of not having access the derivatives of S, relying exclusively function evaluation oracle.
Throughout the rest of the paper, we assume that the objective function is differentiable and bounded from below. We consider the following additional assumptions about f:
Assumption 1. f L-soooth, i.e., Vx, y E Rd, |Vf(()) - vf(v) S L| y112.
Note that Assumption 1, implies the following result (Nesterov, 2013, Lemma 1.2.3):
Vx, E Rd, (f(y) - f(x) - (Vf(x), y 2)1 2 11 x112.
(1)
2
Assumption 2. 30" E ERd f(0") inleeR" ((0).
Assumption 3. f is convex and there existy E Bd such that the sublevel set of I defined by is bounded, i.e.
1. Vx, y RRd, f(v) 2 [(x) (V)())
4

---

Published as a conference paper at ICLR 2025
2. There exists R such that L(c) {x R f(x) S f(c)} is bounded. Assumption 4. f is p-strongly convex, i.e., there exists positive constant such that:
Y R", f(y) 2 f(z) + (V)()) z) 2 1 10--0 ==16-
Note that Assumption implies the following result (Nesterov, 2013, Theorem 2.1.8):
1 Vx E Rd 1 [V f(x) inf
vERe f(v)
(Polyak-F.ojasiewiiz, inequality).
2μ
For the distributions over RR,, we make the following assumptions:
Assumption 5. The probability distribution D on IR satisfies:
1. TD EESDll < co.
2. There exists a norm
for which we can find a constant pp > such that: ||.||o on for
Yu Rd. Eg-D (v. s) 2 pol|u||p-
In (Bergou al., 2020, Lemma 3.4), the validity of Assumption has been established for several distributions including:
ii) For the normal distribution with zero mean and the identity matrix over d as covariance matrix, i.c., D ~ (0, 4):
TD = 1, Eun s) = Vda ||l/2
(ii) For the uniform distribution on the unit sphere in Rd:
TD = 1, BAD Kg
Vena 11
Assumption 6. For all s D IP (1|s|12 S 1) =1
Note that under Assumption 6, we have "D 1. Finally, we add the following assumption regarding involved in Assumption 5:
Assumption 7. PD <
Remark 1. In Section 5, we modify the second condition of Assumption 5 by replacing it with:
There exists constant pDD > 0 such that: Vu Rdd, Ex~DI(u, s)| PD ||0||2-
Since norms equivalent on Rd, this condition is equivalent to the second condition of Assump- tion We note also that Assumption satisfied for distribution distribution (i).
Throughout the paper, the abbreviation "a.s" stands for "almost surely".
CONVERGENCE ANALYSIS FOR THE CLASS OF SMOOTH FUNCTIONS
3.1 CONVERGENCE ANALYSIS FOR THE BEST ITERATE
In this subsection, will assume that Assumptions 1, and hold true. Under these assumptions, we establish that for any > 0, when (0'},> is generated by the STP algorithm using the step size sequence { {- 1 with a > follows that min siinssssslV// [[')]] converges almost surely
This result provided by Theorem which follows from the first finding of at a rate of 2
Lemma that ensures that: E
1 E (f oc.
2
5

---

Published as a conference paper at ICLR 2025
Lemma 1. Assume that Assumptions 1, 5 and 6 hold true. Let {a1)121 be sequence of step sizes satisfying -t=1 oi < cc. Let [6' 1:21 be a sequence generated by Algorithm Then, the following results hold:
EE of [IV]( < <0, a. a.ll I < 00 a.s.
In the Appendix (Lemma 5), we prove that if (X, is a sequence of nonnegative real num- bers that is non-increasing and converges 0, and {az h121 is sequence of real numbers such that EE X, converges, then XT converges 0 at rate of (1/Ei= / since (mingrr ()) satisfies the conditions of this lemma when Et=1 og < co and E 0o, we conclude that in this case, the best gradient iterate converges to 0 at a rate of 1= at). This result is formally presented in Theorem 1.
As result,
Theorem 1. Assume that Assumptions 5 and 6 hold. Let {0' (0') be sequence generated by Algorithm 1, where the step size sequence (o1)111 satisfies the following conditions:
t=1 a < 00,
00
-=1
Then, we have:
min Vf
ISST
ΣE=
In particular, if choose or
with a 0 and e (0, 4), it follows that:
t
1 (
min ESST
a.s.
In (Bergou et al., 2020, Theorem 4.1), the authors established that by using the STP algorithm with a step size sequence rate of O Va
{ v 121" where a > 0, the best gradient iterate converges
expectation
The second result of Theorem I provides similar version of this result almost surely, where both the step sizes and convergence rates are roughly similar.
(vT)
Remark 2. Since all norms are equivalent in finite dimension, for any norm |I-II R2 we can conclude that by selecting a;
o where >> O and e (0, t). the following holds: 12
min VV(')1 15KT
T
Remark 3. In the non-convex setting, the convergence analysis in the previous theorem implies that min <IST ((0))) converges zero almost surely. However, remains uncertain whether the gradient of the last iterate | [(0T)] also converges almost surely to O. In section 3.2, will establish the convergence of the last ilerate of the gradient, both almost surely and in expectation.
3.2 CONVERGENCE ANALYSIS FOR THE FINAL ITERATE
In this subsection, we will assume that Assumptions 1, and hold true. Under these assumptions, we establish that the STP algorithm ensures the almost sure convergence of V I| to 0 and the
convergence of El| V f(0"") to This result holds for any step size sequence (az, J121 such that: and E a
E of
The almost sure convergence result is provided by Theorem 2, while the convergence in expectation is established by Theorem 3. Notably, both of these theorems derived from Lemma I and Lemma 7. (see the Appendix).
Theorem 2. Assume that Assumptions 1, 5 and 6 hold true. Suppose that the step size sequence
satisfies:
E ai 00, t= Oi = OC.

---

Published as a conference paper at ICLR 2025
Let 122 be sequence generated by Algorithm 1. Then, we have: lim [V = ==
a.s.
T
Theorem 3. Assume that Assumptions 1, 5 and hold rree. Suppose that the step size sequence satisfies:
-= a <0, E a4 oc.
xc,
Let J021 be a sequence generated by Algorithm 1. Then, we have:
lim T T-++00
E
Remark 4. In particular, for any (0, 2), the step size sequence (,3t, J121 with a >> 0, satisfies the conditions on step sizes of Theorems and 3.
CONVERGENCE ANALYSIS FOR THE CLASS OF SMOOTH CONVEX FUNCTIONS
In this section we will assume that Assumptions to 3, 5 and 6 hold true. Since f is real-valued, continuous, and convex function, it follows that f a closed proper convex function. Additionally, Assumption 3 guarantees the existence of vector such that the sublevel set of defined by c is bounded. Therefore, we can deduce that all sublevel sets of f are bounded, as shown (Rockafellar, 2015, Corollary 8.7.1). Let 0* be the initial vector of the STP algorithm. In particular, the sublevel set L(O*) is bounded, and forms a compact set of g (because f is continuous).
Let's denote || 1/b as the dual norm of || Il,, defined for all I E TRd by: |10| sup |ell Since + ||0 0* [| is continuous over Rd and L( is compact subset of IR,, we have:
(v.0)
R sup ||0 1 < xo. BEL(0")
Since f is convex, we have that for all 0 E I((!):
(v, 8*)
f(0) - f(0)) < (Vf(0), 0*) s Vf(0))l
sup vER
| < R [
110-8-116
By the construction of the STP algorithm, for all t 2 1, f(0)) s f(ol). Therefore, for all 2 1, of E L(O'), and thus we have:
v # 1, f(0)) f(0)) < R/
(2
This final result serves crucial point for the convergence analysis of Theorem and Theorem 5.
The following Theorems 4 and 5, show the convergence the final iterate f(0") to the optimal value with rate Odd/T) in expectation, and rate approximately o(1/T) almost surely.
Theorem 4, Assume that Assumptions to 3, 5 and 6 hold true, and consider a sequence {0')2 generated by Algorithm 1, where the step size sequence is defined as Ts21 with a > R
We have the following bound: E [[((TT]] - -(00) S T
where
3apD
Laz
(S(D") {((*)) 2 R
cur R
In particular, if pp is proportional to J/ then by taking a pp we obtain a complexity bound of the form O (4)
7

---

Published as a conference paper at ICLR 2025
Note that for the normal distribution (i) with zero mean and identity covariance matrix, as well as for the uniform distribution over the unit sphere (ii), pD is proportional to va
Remark 5. Assume that μrD is proportional to T8. and let 2 2 be constant. We choose such O(ed). Thus, we obtain the convergence rate O ed in
that uD S a S
eRt pD
we get
La²
21 2(
Theorem 4.
Theorem 5. Assume that Assumptions to 3, 5 and 6 hold true. Let 16t It21 be sequence gener-
ated by Algorithm 1, where the step size sequence is given by at 0 7--3 for some 3 E (0, $2)
We then have the the following:
Ve E (23,1), f(0") f(00) =0 TI-c)
STRONGLY CONVEX ALMOST SURE CONVERGENCE RATE FOR STP ALGORITHM
In this section we will assume that Assumptions 1 and hold true. The main results of this section are stated in Theorems and 7, which follow from Lemma 3. When step sizes are obtained by approximating the directional derivatives of the function with respect the random search di- rections, we show in Theorem 6 that f(0") converges in expectation to inføeR" f(0) at a rate of O((1 - 2nd2 )²), and in Theorem 7, we establish this convergence almost surely at rate arbitrarily close to ((11 2nd2 ))), where μ and are the strong convexity and smoothness parameters of the function, and d the dimension of the space. We recall that strongly convex function has unique minimizer, which we denote by 6"
P
The following Lemma 2, controls the decrease per iteration of the value function. It is used control the total decrease of the value function after T iterations given in Lemma 3.
Lemma 2. Assume that Assumptions 1 and 6 hold true. Let h E (1, (1) and let 10' be sequence generated by Algorithu 1, where the step size sequence used is { [1110 -x)) "x)--100" Then have:
Lh
Vt 1, f(0)+1) S $(8") (VS(0"),Ee)P
I, 12 a.s.
2L
Lemma 3. Assume that Assumptions 1 and 4 to 7 hold true. Let h E (1, and let 10') Jo2 be
sequence generated by Algorithm 1, where the step size sequence used is { [110 -x))-((")) Then have:
J121. Lh
VT 2 2, E[((0") (1 (1- PB ))
T-1-i
h -2i
Theorem 6. Assume that Assumptions 1 and 4 to 7 hold true. Let h
(T-
3
and let {0t)22 be sequence generated by Algorithm 1, where the step size sequence used is 11 +h +1==))) "'0''((0') J121. Then we have:
LA-t
22, B[S(0T) [(0))) (1 132111
T-1
s(0") +
(3)
8
h2
2
In particular, if PDD is proportional
1. iee, PDD
K.
for some positive constant K, then by
Va
Va
we obtain rate 0 (11-
aR²
T
taking h
dl
V 2
8

---

Published as a conference paper at ICLR 2025
Theorem 7. Assume that Assumptions and 4 to 7 hold true. Let 102 be sequence
generated by Algorithm 1, where the step size sequence used is { {Ifl0'th th "m)) 122 with
Lh-
00 we have: vs E (0,1), f(6T) 5(0)) = (((0)==(11))))
(11-) (1(0))
h E
a.s.
In particular, if uD is proportional to Ja i.e. PDD Je for some positive constant K, then for all 8 E (0, 1), we obtain a convergence rate of o((1 - Remark 6. Note that for the uniform distribution over the unit sphere, we have pp The
K
= - )²).
v/2nd'
convergence rates for Theorem 6 and Theorem 7 in this case respectively O((1 2ndT. )²) and o(11 sxxL))") ) any (0, 1).
6 NUMERICAL EXPERIMENTS
Let's consider the following optimization problem:
d-1
1 (0,)²
1 (Ba)) 01, initial vector: 0² 0, Σ (0++1 0,)2
min f(0) BER
where d = 500. This objective function was used in Section 2.1 of Nesterov et al. (2018) to prove the lower complexity bound for gradient methods applied to smooth functions. By running multiple trajectories for the three algorithms: the STP algorithm, the RGF algorithm (Nesterov & Spokoiny, 2017), and the GLD algorithm (Golovin et al., 2020), the objective is to simulate the convergence of the last gradient iterate for each trajectory and also illustrate the rate of convergence of the best gradient iterate.
RGF Algorithm: This algorithm starts with initial vector 0² and iteratively updates it according to the followingrule rule g++ 4t - ha f18' =((x)) Ue, where 4e a normally distributed gaussian vector. In this implementation, we set μ4 10-4 and h 1. where s 4 represents the smoothness parameter of the objective function.
This algorithm proceeds as follows: it starts with an initial point 02, a sam- pling distribution D. and a search radius that shrinks from maximum value R to a minimum value r. The number of radius levels is determined by K = [log2 (f) For each iteration t, the algorithm performs ball sampling trials, where it samples search directions x from progres- sively smaller radii Vk 2- R2, < k < K, and then updates the current point by selecting the w that results in the minimum value of the objective function. The update step is given by: gt-1 arg min (00,00 (0*,0"+00,-- +0 f(y). For this algorithm, we use the standard Gaussian distri- bution D and set r = 10-5 and R 10-4.
GLD algorithm:
set the step sizes to be a₂ fulor, and the random search directions sy generated uniformly on the unit sphere of igd The chosen step sizes adhere to the form provided in the second result of Theorem 1, where = 0.01. In our experiment, we run 50 trajectories for each of the three algorithms, all starting from the same initial point O. We simulate l f(0') Ill)) as a function of the number of iterations, as well as the elapsed time in seconds. Additionally. to verify the rate assured by Theorem for the STP algorithm, we simulate 0.04 minesT [[V as function of the number of iterations.
For the STP algorithm,
Figure/ and Figure 2 illustrate the logarithmic decay the gradient norm with respect to both iterations and elapsed time, highlighting its convergence to zero across all trajectories for the three algorithms. Notably, STP and RGF demonstrate competitive performance, with STP being slightly better, in terms of the number of iterations and the time required to achieve given accuracy, outper- forming the GLD method in both metrics. This similarity between the performance STP and RGF reflects their similar theoretical complexity bounds. It is important note also that each itera- tion, the STP and RGF methods require two function evaluations, while the GLD method requires [log, [4)] function evaluations.

---

Published as a conference paper at ICLR 2025
In Figure 3, observe the convergence of the best gradient iterate to 0 at rate of o ( across all trajectories for the three algorithms. In particular, this illustrates the rate obtained for the STP algorithm.
STP Algorithm
GLD Algorithm
RGF Algorithm
-0.2
1091
-0.4
1
-0.4
-0.4
-0.6
-0.5
-0.0
-0.8
-0.5
-0.8
-1.0
-1.0
-1.0
-12
-1.2
-1.2
-1.4
-144
-1.4
10000
20000 30000 40000 50000
10000
20000 30000 40000
50000
10000
20000 30000 40000 50000
Iteration 7
Iteration 7
Iteration
Figure 1: Logarithmic decay of gradient norm vs. Iterations.
STP Algorithm
GLD Algorithm
RGF Algorithm
0.0
-022
-0.2
-04
(091)))010
1
logi 1
-0.6
-0.6
-0.8
-0.6
-0.8
-10
-1.0
-1.0
-12
-1.2
-12
1.4
1.4
1.4
20
40
60
20
80
Time (seconds)
Time L (seconds)
Time (seconds)
Figure 2: Logarithmic Decay of gradient norm vs. Time.
STP Algorithm
GLD Algorithm
RGF Algorithm
35
35-
35
10:55 min 1
30-
70:45 min 1
30-
70.4 min Moouu
30-
25
25
25
20
20
20
15
15
10000
20000 30OQU ADU00
50000
10000
20000
40000 Iteration
30000
50000
10000
20000 Iteration
30000 40000 50000
Iteration T
Figure 3: Convergence rate of the best gradient iterate.
REFERENCES
Ya Alber, Alfredo N lusem, and Mikhail V Solodov. On the projected subgradient method for nonsmooth convex optimization in hilbert space. Mathematical Programming, 81:23-35, 1998.
El Houcine Bergou, Eduard Gorbunov, and Peter Richtárik. Stochastic three points method for unconstrained smooth minimization. SIAM Journal on Optimization, 30(4))2266-2744, 2020.
Dimitri P Bertsekas and John N Tsitsiklis. Gradient convergence in gradient methods with errors.
SIAM Journal on Optimization, 10(3):627-642, 2000. 2000.
10

---

Published as a conference paper at ICLR 2025
Soumia Boucherouite, Grigory Malinovsky, Peter Richtárik, and El Houcine Bergou. Minibatch stochastic three points method for unconstrained smooth minimization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 20344-20352, 2024.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization 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 R Conn, Katya Scheinberg, and Luis N Vicente. Introduction derivative-free optimiza- tion. SIAM, 2009.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM journal on optimization, 23(4):2341-2368, 2013.
Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gra- dientless descent: nigh-dimensional zeroth-order optimization. In ICLR, 2020.
Eduard A. Gorbunov, Adel Bibi, Ozan Sener, El Houcine Bergou, and Peter Richtárik, A stochastic derivative free optimization method with momentum. In ICLR, 2020.
W. Royer, L. N. Vicente, and Zhang. Direct search based on probabilistic descent. SIAM Journal on Optimization, 1515)1155-1551, 2015, doi: 10.1137/14096100 602. URL https: / / //oii. 1117/100.113//44991116
Gratton, C.
Jakuh Konečný and Peter Richtárik. Simple complexity analysis of simplified direct search. arXiv preprint arXiv:1410.0333 003000 2014.
Jeffrey Larson, Matt Menickelly, and Stefan M Wild. Derivative-free optimization methods. Acta Numerica, 28:287-4044 2019.
Jun Liu and Ye Yuan. On almost sure convergence rates of stochastic gradient methods. In Confer- on Learning Theory, pp. 2963-2983. PMLR, 2022.
Sijia Liu, Bhavya Kailkhura, Pin- Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
Julien Mairal. Stochastic aajooization-minimizzaii algorithms for large-scale optimization. Ad- vances in Neural Information Processing Systems, 26, 2013.
Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter Bartlett, and Martin Wain- wright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. In The 22nd international conference on artificial intelligence and statistics, pp. 2916 2925.. PMLR, 2019.
Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost sure conver- gence of stochastic gradient descent in non-convex problems. Advances in Neural Information Processing Systems, 33:1117-1128, 2020.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Lam Nguyen, Phuong Ha Nguyen, Peter Richtárik, Katya Scheinberg, Martin Takáč, and Marten van Dijk. New convergence aspects of stochastic gradient algorithms. Journal of Machine Learn- ing Research, 20(176):1 2019.
Ralph Tyrell Rockafellar. Convex analysis:(pms-28) 2015.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as a scalable alternative reinforcement learning, arXiv preprint /rXiv:/703.03800 2017.
11

---

Published as a conference paper at ICLR 2025
Othmane Sebbouh, Robert M Gower, and Aaron Defazio. Almost sure convergence rates for stochas- tic gradient descent and stochastic heavy ball. In Conference on Learning Theory, pp. 3935-3971. PMLR. 2021.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11,2) 2017.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2012. doi: N0.1109/ROO..2012.633
Chun-Chen Tu, Paishun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho- Jui Hsich, and Shin-Ming Cheng. Autozoom: Autoencoder-base zeroth order optimization method for attack- ing black-box neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 742-749, 2019.
Ryan Turner, David Eriksson, Michael McCourt, Juha Kiili, Eero Laaksonen, Zhen Xu, and Isabelle Guyon. Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020. NeurIPS 2020 Competition and Demonstration Track, pp. 3-26. PMLR, 2021.
Luis Nunes Vicente. Worst case complexity of direct search. EURO Journal on Computational Optimization, 1(1):143-153, 2013.
Tianyu Wang and Yasong Feng. Convergence rates of stochastic zeroth-order gradient descent for') ojasiewicz functions. arXiv preprint 10XXi::2200.16999 2022.
A
APPENDIX
Lemma 4. (Bergou al., 2020, Lemma 3.5) Assume that Assumptions 1, and hold true and let (0') h221 be a sequence generated by Algorithm 1. We have:
La
(( 0*) f(0') PPool
Proof of Lemma 1. Let / 2 1. By Lemma 4, we have that:
(((())+)) 0*] < s(0') /,)==|\//(0'|1 + La
au By taking the expectation, we get: B[f( < E / Lo? It follows that:
[[)(() 10000))017000011338///0)))-111)1 La
(4)
By construction of the algorithm the sequence (f(0')) is non-increasing, and since we assume that is bounded from below, have that (IE (6) non-increasing and bounded from bellow, and thus converges. As a result, we have: 2 [ - < co. Knowing that
Eie a? < oc, we conclude from equation 4, that
a. [IV)())) xo.
We deduce also that E D2 a a Vf
Σ a. V < co, which implies that: 0 |) | < aass
12

---

Published as a conference paper at ICLR 2025
Lemma 5. Let (X1 be sequence of nonnegative real numbers that is non increasing and converges to O, and let {ar)22 be a sequence of real numbers such that Ets1 axX, converges. Then, we have:
XT= =0
Ei=1 04
T
Proof. For all T 2 1, we define UT XT E
Oi and RT Ei=r aiXi We then have:
T
Ur
xx
Σ
R Ri+1) X;
1m1
Let T 2 2. We have:
T
T
1
UT= XT
R1
R
X;
X,
1=1
T
T+1
= XT
R
X
1=2
RT+1
Xx
R1
RA
X1
XT
X;
X
1=2
XT
R1
RT+1 + Xx
Ra
X1
X;
X
To prove --m UT 0, suffices to show that:
T
lim T +00
Xr
> Ra X2
1
=
X1-1
Let > 0 and To 2 such that for all T 2 To, we have RT
S. Let T > To. we have:
T
To
T
X1
R
1
X1
R
1
+ Xx
Σ
X1
X
X,
X
2
X,
Xi-1
2
1m2
i= To+1
To
1
1
EXT 1
1
Xx
R
X,
X1-1
XT
XTa
To
1
1
XT
Σ
R
)
+
(1
X,
X;-1
2
XTo
1=2
1
1
S XT
Σ
R
X,
X,
2'
2=2
As liim +00 Xx- = O, there exists T₁ > To such that for all T 2 Tı,
T
To
XT
R₂
XT
R
6
X;
X
X,
X;-1
2
i=2
2=2
Therefore limm-++0o X7
Ra 1
= 0, and we deduce that:
X;
X1-1
Xy =
as T + +00.
5 T
Σ 01
13

---

Published as a conference paper at ICLR 2025
The following lemma, which is classical result about Riemann series, will be needed in the proof of Theorem
Lemma 6. For all a (0, 1), we huve: Et=
Tl I-a'
Proof of Theorem 1. Let define XT min (())l for all T 1. Since Σt=1 of oc, according to Lemma we deduce that _t=1 a,X; of nonnegative real numbers that is non increasing, then, by proving limy-+-o XT = 0 a.s., using lemma 5, we can deduce that:
it clear that (Xr hr sequence
XT =
a.s.
Now, we prove that Jim Xy a.s. According to Lemma we have E au aallVf(0))l <
T-+00
a.s. Thus, it follows that:
{min [VS() KT
Σ 0n is bounded almost surely.
Since lim Et= 04 to0, we can conclude that:
T-4000
lim XT lim min [V]'')> 0 a.s.
Therefore, we establish the first result of the thcorem. The second result is obtained by choosing (as (12) defined by a, + In this case, we have Σ 04 oo, while Σ of <
Using Lemma 6, we have
T
T
12
Therefore,
1 T
min SSKT
Lemma 7 is first presented in (Alber et al., 1998, Proposition 2) and again in (Mairal, 2013, Lemma A.5), along with new proof. We provide new, simpler proof of this lemma that is more straight- forward than those presented in these references.
Lemma 7. (Alber et al., 1998, Proposition 2), (Mairal, 2013, Lemma A.5) Let {ar (be)ea be two nonnegative real sequences. We have:
Σ Dte abb co. Eie dr 00, There exists 2 0 such that |b++1 - bil < Kay.
lim bc 0. 6-0+00
Proof of Lemma 7. First, note that for all no 2 1, have inf b, 0. Indeed, sup- pose for contradiction that inf,zng b, > O. this case, we would have for all n 2 na. b, 2 an infm2n bm, which implies that the series Σ an cannot converge, since _ On oc and 2 1, we have inf bn = in infmmnobm bm > O. This contradiction implies that for all nn
Let O. Let no 2 1 such that for all 2 no we have E ands S f
The goal is to prove that for all n 2 no. b, < e. Let n 2 no. If b, $ 5. then trivially b, S e. Now assume that b,, 5.
14

---

Published as a conference paper at ICLR 2025
We have infa2n bt O, then take the smallest index m such that 6m S 2. We have:
1m
Hnl
S
Boet
imn
K
a5
Σ
K
0i
iE tE(n,..,tm-1yy 111,,122
2K
Σ
a;b;
1E(n...m-1)..b 11,b,
2K
20
S
a;b;
Therefore, by the triangle inequality, we have:
6
bn S bm
S.
2
Thus, for all n 2 no. we have bn S e, and consequently, we deduce that 1 bn = 0.
Proof of Theorem 2. Consider >> 0 satisfying: ||-1| S CCll-lla
Let t 2 1. We have that:
/|| -V (0))lll
- [VS(0t+)) - -
I CL1100t1- - 0'112 (because f is L-smooth)
= CLaaelseell
S CLar a.s. (because assume Assumption 6 holds true)
Therefore, we have that for all 1 2 1: P (IIl V -
IV (0))l=) S &CLor) = 1.
Thus: IP (vt 2 1, v (0(+1)
V f |l S ClLr)) 1.
au V
I|l < oo a.s, (by Lemma because Σee ag < 00)
Given that
Or xc.
Using Lemma 7, with {athez playing the role of {ath2ı and [[V/f(())))))) playing the role of (b. we conclude that:
lim T-+20
|V](0")) = a.s.
Proof of Theorem 3. Consider C > 0 satisfying: ||-I|p < C/I-112-
Let t 2 1. We have that:
E Vf (0++)|11 E Vf [I]]
< E
V (0)) f/V (0l+1) I
< V (0') V (0+
< CLE [110**1 [0]]]] (because f is L-smooth)
= CLa.E [||s
S CLa, (because assume Assumption 6 holds true),
15

---

Published as a conference paper at ICLR 2025
where in the first inequality, we used Jensen's inequality. So, proved that: f (0]))) - EI| Vf (0*) Dlll - CLa..
Vt 2
Now, given that Ei=1 or (l) < 20 (by Lemma because Σi=1 of < oo), and that Dt=1 Oi = oc, we use Lemma 7, with (0 playing the role of (ar)e2 and [ ((0))lee playing the role of (br)11, to conclude that
lim [[[V]((")]l) =0 T++00
Lemma 8. (Liu & Yuan, 2022, Lemma 1) If {Yi)22 is a sequence of nonnegative random vari- ables adapted to a filtration {oer2 and satisfying:
E E Fil S (1 aaa) Yi + cz for all t t21,
where 04
0 (2x ( for some B E (0, and and 0z are positive constants. Then, for any
C (2,,1)
= t
a.
Proof of Theorem 4. By Lemma 4, we have that:
11 2 1, B[S(0++)) | 0*) s 5(0') pDD /V/(0') + Lai
2
Knowing from equation 2 that: Vt 2 1, f(0") f(00)=))000)))))))>)))) S R|| f( )|b, we have:
Vt N 1, E[f(0' f(0") 001 < (1 at ) ) (f(0") - f((0)) + Taking the expectation, and knowing that az a we get:
Lo
2
14 2 1, E [5(0+t]- - [(0*)] S (1 aHD
E [5(0*) [(0')]
La
(5)
Rt
212
:6++
:=6;
If E (1,
[
1}. 6, E[S(0') -(00) < 1(0)) 1(0)) S (( (LaRP) (11 -(00)-1(0))
Then
aHD
3oHD f(0)) - f(0)
CHD
3apD
E [1,....
+ 1}, 6z <
because
+ 1 5
+2
R
R
R
R
R
Let's denote and as follows: max
(3aD R
(f(ll) 1 f(()))
La K
and
pp
We
2(
1)
R
have:
apD
VI (1,
+ 1}, 8, 5
(6)
R
T.
We will prove by induction that:
< a
14
2
+ 1, 8,
R
For t roug + 1, we have that:
Let t 2 [ayd] +1. Assume that 5z < 2 and let's prove that 8.t1 S 4+1
We note that 1 - app > 0.
From equation 5, we get 6, < = d,41 < _
abn
Lad
We have also the following equivalence:
12
2
abu La 2
0
abix
La²
-a
S
2
t
++1
12
21
t(t
+ 1)
La²
at
aba +
<
2
1-1
16

---

Published as a conference paper at ICLR 2025
Let's prove that the last assertion is true. We have:
-at
aal
S t+1 -bba + alba - 1)
t+1
aba + La²
-at
2
++1
The last implication comes from a(ba 1) max
(ba 1
Bayp (S(0t) - 5(00)) La?
20
We deduce finally that 6141 S 1+1. Therefore, we get: VT > can + BiS(0 - 1(00) S 7. and using equation 6, we deduce that:
a VT 2 B[ 5(0)) S T
In particular, if ur proportional to
then by taking a = 2ft ppp
we have:
v7
T, 4 O(d),
max( 3apd (f(0t) - f()))),
La²
1
R therefore B[f(0")] - f(0)) = O
2( 2Rp
1)
2
Proof of Theorem 5. By employing the first part of the proof of Theorem 4, have that:
Vt 2 1, B) f(0") (0) $ (1 (1-ay
PD R
(f(0") f((*)) + La?
2
Using Lemma 8, we deduce that when ar = -O(T-=) with 0 E (0, } we get:
Ve E (20, 1), f(8²) - f(8) = ol (I-)) a.s.
Proof of Lemma 2. Let t 2 1. Using the smoothness property in equation 1, we have:
( f(0t + a,s;) < f(0²) ) + a. f st) + [afl \5(0s a1 S 1(0') -. (V/ 8,) + 0
Then f(0+1)) S f(0') ar / (Vf((*), st)l+ = By replacing a by its expression, and using Assumption 6, we have:
f(gt+2) < f(0)) 15(0' + h h - f(09)
L (5(0' +h 5(09)
(V siYl
Lh-t
Lh-t
$ <((0)) 15(0' + h (s1s f(00) (V)(0') si)
Lh-t
T. (1((0' + (1 f(0)) -10) ((V/ A-
2
Lh
[f(0 + hs'ss) f(0') (V)(0),, 's)
(Vf(8")
Lh 21
2Th 2t
(V)((%) s2)12
L
|5(0' + -1 [(0)) I(V (QO)) 11 h
<0(0)
a.s.
2L
2
Lh-t
(VI(0)),
L
[ + (() S(09) (VS(09), (
<S(0')
a.s.
2L
2
Lh-
I(V (0*), ((*),,8)) 12)
L
LA 1|s,111
2
<f(00)
2
a.s. (using property equation
2L
2
Lh
(V ), 1x)
L
<0
10
-21
a.s.
2T.
8
17

---

Published as a conference paper at ICLR 2025
We conclude that: 11 2 1, 1(0--1) & 1(00) KV )v)))))))))
1/11 a.s.
22
Proof of Lemma 3. Let 2 1. By Lemma 2, we have:
f(0 S f(0') KV (VV) 86)l
Lh-
+
a.s.
2L
Using the tower property:
[ (0") 81) s1>1 = BAND (V/ (0'), ..)) [00]
E
(BanD [[<V (0) ]()s 2
Jensen Inequality
(0*) [
Assumption
holds that: E [ (0C- 1)] - r(0') s B1 -(0') t E
|V/ (0 (00)1
14-
By Assumption 4, we have [V 2 2p (f (0t) -((0)) ()0 then:
E (0++1)-((0)) s (1 1 uBl1
E [ - -((0)] + Lh-
Thus by induction we obtain:
VT 2 2, B(1(0))) < (1 (1- 18/11 T-1
T-1 Σ ==1
1
T-1-i
1
h h-
L
L
Proof of Theurem 6. Since h E
V1 "3 00
holds that: VT 2 2,
0.
12
1-
Then, using Lemma 3, we get:
T-2
11
1-
L
VT 2 2, E[f(0") -(00))))(0011---
1
(F(0))-((0'))
+
L
812
ha
1
[((0)) f(00)
I
L
h22
which gives the desired inequality.
In the particular case where K. Vi. by replacing h and by their formulas, we obtain the
desired rate o ((1- nK2
T
dL
Proof of Theorem 7. Let (0, 1), consider a 8 uee By multiplying the inequality (3) by --T T we get that for all 2 2:
Ela-" (f(0") f(0))) < -1 a a1
12211 -
T-1
a'
(f(0z) f(()))
a
L
8 122
18

---

Published as a conference paper at ICLR 2025
As a -1
E (0,1) it holds that:
b
1-s "D"
E
Σ T=2
T (5(07) -(00)) Σ
Bla T (((0T) < co.
T=2
Therefore:
ΣT=2a (f(0P) - -(00)) < 00 a.s., and we conclude that:
f(0²) -((0) = =aaa) a.s.
19


Reviews:
[{"review_id": "TOGJHfbjem", "reviewer": "Reviewer_3UjN", "summary": "This paper analyzes almost-sure convergence for the derivative-free stochastic three points (STP) algorithm in (Bergou et al., 2020), where only the convergence in expectation was studied. The convergence in expectation does not guarantee convergence of individual instance of trajectories, which is why, for example, extensive research on almost-sure convergence has been conducted for SGD. This paper's study of STP, therefore, aligns with recent theoretical advancements in SGD. In particular, this paper provides the almost-sure convergence results for three standard classes of functions, as summarized in Table 1.", "questions": "- Lines 111-112: Although it is straightforward, please explicitly state the consequence of the result.\n- Line 124: $\\theta$ denotes both the iterates and the step size parameter, and I suggest using other letter for the step size parameter.\n- Remark 2: This seems redundant and I suggest removing it.\n- Lemma 4: This does not seem necessary here, which is only used in the proof in the Appendix. I suggest moving it to Appendix.\n- Remarks 7,8 and 10: They discuss the condition that Assumption 3 can be satisfied. I believe that they can be simply discussed right after Assumption 3, or can be more clearly and briefly stated in the remarks.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper provides the first almost-sure convergence analysis of the STP method for three standard classes of functions, a non-trivial achievement. This analysis guarantees convergence of each trajectory instance, making it valuable both theoretically and practically.", "weaknesses": "- Motivation: The focus on STP in this paper is not well motivated in the abstract and introduction, aside from mentiong its low per-iteration complexity. Is the STP widely used in practice? Given its simplicity and strong theoretical guarantees, I cannot see why this would not be considered by practitioners. I suggest that the authors further elaborate on the theoretical and practical importance of studying the STP.\n\n- Comparison to other existing derivative-free methods: Although this paper focuses on the STP, it would have been helpful to include comparisons or discussions of the almost-sure convergence (rate) analyses for other existing derivative-free methods, if available. Without these, it is difficult to locate this work within the broader literature.\n\n- Experiment: What is the purpose of this experiment? It seems quite orthogonal to the paper's theoretical contributions. It looks like it was added to appeal to practitioner reviewers, but I believe it may ultimately satisfy neither theory nor practitioner reviewers. I suggest revising the experiment section to better align with the paper's main contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "QmHSaPVFpL", "reviewer": "Reviewer_dTaK", "summary": "This paper establishes the almost sure (and last iterate) convergence of the stochastic three-point algorithm for zeroth-order optimization. The paper considers smooth nonconvex, convex, and strongly convex settings and gets the results under three different settings, respectively. Numerical experiments demonstrate the performance of the proposed method.", "questions": "1. In the nonconvex case (Theorem 1), lower-boundedness (A2) is not assumed. But on line 624 in the appendix, the authors use the assumption that $f$ is bounded from below. \n2. A7 seems to be an artifact of analysis. Could you provide more intuitions behind it?\n3. Results in section 4 require the initial point to lie in the sublevel set. Here the cost of finding such an initial point is not discussed. Could you elaborate more on this?\n\n**Minor issues**\n\n1. Line 139\n\n   There seems to be an additional 2 in the complexity.\n\n2. Line 146\n\n   The Assump column does not match all the results in the paper (e.g., Theorem 7 in section 5 mentions \"Assumption 1 and 4 to 7\"). Also, assumption 7 does not appear in the table.\n\n3. Line 146, 533\n\n   Please put the caption of the table at the top.\n\n4. Line 204\n\n   The statement of the examples seems incorrect and inconsistent with [1]. The covariance matrix in [1] is $I_d / d$  instead of $I_d$.\n\n   For any arbitrary => For any.\n\n5. Line 318, 372\n\n   $\\ast$ and $^\\star$ are inconsistent.\n\n6. Line 890\n\n   $m$ is undefined.\n\n**References**\n\n[1] Bergou, E. H., Gorbunov, E., & Richtarik, P. (2020). Stochastic three points method for unconstrained smooth minimization. *SIAM Journal on Optimization*, *30*(4), 2726-2749.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-written, with technical results clearly presented and explained. Also, different settings are considered in the paper.", "weaknesses": "My major concern is the technical novelty of the paper.\n\n1. Insufficient technical contribution.\n\n   Although the paper considers multiple settings and gets almost-sure convergence results, the techniques seem to be a combination of [1] and other papers that establish almost-sure convergence of SGD in different settings. Especially the results in section 3 and 4 look less surprising, since most of them are obtained by verifying some conditions and invoking an existing almost-sure convergence result from the SGD literature. \n\n2. Presentation issues.\n\n   The paper contains many technical results, either proven in this paper or cited from other papers. However, there is not sufficient explanation after each main result. This may make the results less accessible to the readers.\n\nOverall I think this is a solid work, and I would like the authors to further clarify the technical contributions in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "6oWZf2gvvH", "reviewer": "Reviewer_tFkj", "summary": "Convergence analysis of the stochastic three points (STP) algorithm is studied. The rates for different classes of functions are shown. A almost sure convergence rate arbitrarily close to $O(1/\\sqrt{T})$ is shown for smooth functions.\nAnd almost sure convergence rate arbitrarily close to $o(1/T)$ and in expectation a rate of $O(d/T)$ is shown for smooth convex functions. For the class of strong convex functions, a rate of $O((1-\\mu/dL)^T)$ in expectation and a rate arbitrarily close to $o((1-\\mu/dL)^T)$ for almost sure convergence is shown.", "questions": "1. Please add a table comparing the convergence rates (both in expectation and almost sure) of STP, RGF, and GLD for each function class studied. Also please discuss how STP's rates compare to known optimal rates for each case. This is important as it would provide valuable context for the significance of the STP results.\n\n2. Please add a paragraph or two in the introduction highlighting the key advantages of STP over other zeroth-order methods, such as its linear dependence on dimension compared to quadratic dependence for deterministic direct search methods. This would help readers better understand the importance of studying STP's convergence properties.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Paper is well-written. Convergence rates of the STP algorithm for smooth, smooth convex and smooth strongly convex functions are shown.", "weaknesses": "The results are incremental. How does the convergence rate of STP compare with other methods both in expectation and almost sure. For example with RGF or GLD which is compared in the experiments ? This could be discussed or given as a table. What about the optimal convergence rate in each case ?  A brief discussion about the advantages of STP algorithm in the introduction would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)