A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Authors: Kunjie Ren
Luo Luo
Venue: ICML 2025 poster (2025)
Keywords: zeroth-order optimization
stochastic convex optimization
parameter-free optimization
Primary area: theory->optimization
TL;DR: We propose and analyze a parameter-free and near-optimal zeroth-order algorithm for stochastic convex optimization.

Abstract: This paper studies zeroth-order optimization for stochastic convex minimization problems. We propose a parameter-free stochastic zeroth-order method (POEM), which introduces a step-size scheme based on the distance over finite difference and an adaptive smoothing
parameter. Our theoretical analysis shows that POEM achieves near-optimal stochastic zeroth-order oracle complexity. Furthermore, numerical experiments demonstrate that POEM outperforms existing zeroth-order methods in practice.

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Kunjie Ren
Luo Luo
Abstract
of the objective function via random directions (Kiefer & Wolfowitz, 1952; Ghadimi & Lan, 2013; Duchi et al., 2015; Nesterov & Spokoiny, 2017; Nazari et al., 2020; Gasnikov ct al., 2022; Lin et al., 2022; Rando et al., 2024; Chen et al., 2023; Kornowski & Shamir, 2024). For stochastic convex problems with Lipschitz continuous components, Nesterov & Spokoiny (2017) first developed random search methods that achieve suboptimal convergence rates. Subsequently, Duchi et al. (2015) proposed a stochastic algorithm that constructs finite differences using two random sequences, improving the dependence on problem dimension compared to Nesterov Spokoiny (2017). They also established a lower bound, demonstrating that their algorithm achieves near-optimal stochastic zeroth-order oracle (SZO) complex- ity. Building on this, Shamir (2017) introduced an algorithm using a single random sequence drawn from the uniform distribution over the unit ball, which is optimal and easy to implement. Finite difference methods have also been broadly applied to smooth optimization problems (Ghadimi & Lan, 2013; Nesterov Spokoiny, 2017; Duchi al., 2012b; Balasubramanian & Ghadimi, 2018), as well as to nonsmooth and nonconvex settings (Lin et al., 2022; Chen et al., 2023; Kornowski & Shamir, 2024). Despite these ad- vances, existing zeroth-order optimization methods (Kiefer & Wolfowitz. 1952; Ghadimi & Lan, 2013; Duchi et al., 2015; Nesterov & Spokoiny, 2017; Nazari et al., 2020; Gas- nikov et al., 2022: Lin et al., 2022; Rando et al., 2024) face several limitations. A key challenge is their high sensitiv- ity parameter settings. Achieving optimal convergence rates typically requires carefully tuned step sizes that de- pend on prior knowledge of problem properties (such as the Lipschitz constant) and the iteration budget. In addition, the smoothing parameter used in the finite difference often depends on the target accuracy or decays rapidly, which can lead to numerical instability in practice.
This paper studies zeroth-order optimization for stochastic convex minimization problems. We propose a parameter-free stochastic zeroth-order method (POEM), which introduces a stepsize scheme based on the distance over finite differ- ence and an adaptive smoothing parameter. Our theoretical analysis shows that POEM achieves near-optimal stochastic zeroth-order oracle com- plexity. Furthermore, numerical experiments demonstrate that POEM outperforms existing zeroth-order methods in practice.
1. Introduction
This paper studies the stochastic optimization problem
min fx) _ [x==|F((x; {)] xEX
(I)
where the domain X' C Rdd is compact convex set, the ran- dom variable & follows a distribution E, and the stochastic component function F(x: {) is convex and Lipschitz con- tinuous in x over X' for any given g. We focus on stochastic zeroth-order optimization for solving Problem (I), where the algorithm can only query stochastic function values. This setting is particularly relevant when accessing (stochas- tic) first-order information is expensive or infeasible. Such scenarios arise in various applications, including bandit optimization (Flaxman et al., 2004; Agarwal et al., 2010: Shamir, 2017), adversarial training (Goodfellow et al., 2014; Shaham et al., 2018), reinforeement learning (Balasubra- manian & Ghadimi, 2018; Mania et al., 2018), and other black-box models (Liu et al., 2016; llyas et al., 2018).
Finite difference methods are widely used in zeroth-order optimization, where they estimate the first-order information
We desire develop adaptive stochastic optimization meth- ods that remove the need of parameter tuning. Most existing work focus on first-order methods. For example, Rolinek & Martius (2018); Vaswani et al. (2019); Paquette & Schein- berg (2020) introduced line search techniques for stochastic optimization. Tan et al. (2016); Berrada et al. (2020); Loizou et al. (2021); Wang et al. (2023) extended the Barzilai- Borwein (BB) step size (Barzilai & Borwein, 1988) and the
'School of Data Science, Fudan University, Shanghai, China "Shanghai Key Laboratory for Contemporary Applied Mathe- matics, Shanghai, China. Correspondence Luo Luo <lu- edu.en">.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Polyak step size (Polyak, 1987) to stochastic settings. For training deep neural networks, adaptive algorithms such as AdaGrad (Duchi al., 2011), I), Adam (Kingma & Ba, 2014), and their variants (Tieleman, 2012; Zeiler, 2012; Shazeer & Stern, 2018; Wang et al., 2024; Zhang et al., 2025) exploited the specific problem structure and have achieved success in many applications. However, these methods still rely on appropriately chosen initialization parameters, which can significantly influence convergence behavior, both in theory and in practice.
2. Preliminaries
In this section, we formalize the problem setting and intro- duce the smoothing technique in zeroth-order optimization.
2.1. Notation and Assumptions
Throughout this paper, we use || || to denote the Euclidean
norm. The unit ball is defined as B - {u E R. ||u|| - 1}
and the unit sphere as gd-1 & {v E Rd ||v| denote by U(Bd) and U( the uniform distributions on the unit ball and the unit sphere, respectively, Additionally, we use the notation (-) to suppress logarithmic factors.
1 We
Ideally, we aim to design a parameter-free optimization method that achieves near-optimal convergence rates while requiring minimal knowledge of problem-speciffe properties (Streeter & McMahan, 2012; Defazio & Mishchenko, 2023; Lan al., 2023; Li & Lan, 2023). Several parameter-free methods for stochastic convex optimization have been de- veloped using online learning techniques (Luo & Schapire, 2015; Orabona & Pál, 2016; Cutkosky & Orabona, 2018; 8; Bhaskara et al., 2020; Mhammedi & Koolen, 2020; Jacobsen & Cutkosky, 2022), though their implementations are often quite complex. In practice, Orabona & Tommasi (2017); Chen al. (2022) applied coin-betting techniques within the classical stochastic gradient descent (SGD) framework, achieving strong empirical performance in training neural networks. Later, Carmon& & Hinder (2022) showed that us- ing a bisection step to adaptively determine the step size in SGD yields a parameter-fin algorithm with near-optimal convergence rates. Building on this work, Ivgi et al. (2023a) proposed parameter- free step size schedule called Distance over Gradients (DoG), which adjusts step sizes based on the distance from the initial point and the norm of stochastic gradients (You et al., 2017: Shazeer & Stern, 2018; Bern- stein et al., 2020). DoG achieves near-optimal convergence rates and performs well in practice. However, all existing parameter-free methods are designed for first-order opti- mization. Extending these methods to the zeroth-order set- ting presents additional challenges, particularly the need to eliminate tuning for both the step size and the smoothing parameter, as well as to carefully control the dependence the problem dimension in the convergence rates.
We make the following assumptions for Problem (1). Assumption 2.1. The domain X' C Rd is compact and convex. Furthermore, we denote the diameter of X' by
Dx - max ||x yll < co. x.yEA'
Next, we define the Euclidean projection onto the domain. Definition 2.2. For any point x E Rdd the Euclidean projec- tion onto the compact convex set X' Rd is given by
xx - arg min ||x - y/|-
yEX
Under Assumption 2.1, the objective function attains its minimum the compact set X. Hence, define the optimal solution to Problem (1) as follows.
Definition 2.3. Let x, E 2' be an optimal solution to Prob- lem (1) such that fx.) = minxex fxx).
We aim for the iterative algorithm to find approximate solution to Problem (I), which is defined as follows.
Definition 2.4. A point is called an e-suboptimal solution to Problem (1) if, for a given c > 0, it satisfies
f(x) - fxx)) S.c.
We also assume the stochastic component F(x; {) is convex and Lipschitz continuous with respect to x. Assumption 2.5. The stochastic component F(x: {) is convex in x for each fixed &.
In this paper, we propose a parameter-free free stochastic zeroth- order method (POEM), which introduces a stepsize scheme based on the distance over finite difference and an adap- tive smoothing parameter. For the stochastic convex op- timization (1), show that the initialization affects the convergence rates only by logarithmic factor. We estab- lish high-probability convergence guarantees, demonstrat- ing that POEM achieves near optimol SZO complexity. A comparison of POEM with related methods is presented in Table We also study the problems with unbounded domains and show that an ideal parameter-free algorithm is impossible in such settings. Finally, conduct numerical experiments to validate the practical effectiveness of POEM.
Assumption 2.6. There exists a constant L 2 0 such that for all x, y E IRd, and any fixed e. the following holds
[[F(x;)) Fly: S T.I|x - y/|-
We further assume that the algorithm for solving Problem (1) has access to a stochastic zeroth-order oracle that returns unbiased stochastic function value estimates at two points.
Assumption 2.7. The stochastic zeroth-order oracle returns the stochastic evaluations F(x: {) and Fly: {) for given points x E dd and y E Rd, such that Eg [F(;; {)] = fxx and (y: = f(y), where & drawn from E.
2

---

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Table 1. We present the S70 complexity, step size ?], and smoothing parameter je for obtaining an e-suboptimal solution Problem (1), where denotes the iteration index. 7 is the total iteration budget, and and G2 are defined in Algorithm 1.
Algorithms
Parameter-Free
SZ0 Complexity
RSNSO
L'
d 80\
No
Nesterov & Spokoiny (2017)
62
dLvT
T
TPGE Duchi et al. (2015)
dL
Dx [Vdlog(2d)
Dx and
Dx
No
6²
d
TPBCO Shamir (2017)
dI, d3
Dx
d
x
2²
LvTT
T
POEM
dI,² D
Fr
d
Theorem 4.9
Yes
e²
vG.
" t+1
Lower bound Duchi al. (2015)
DdL'D 2
Ω
1 RSNSO (Nesterow & Spokoiny, 2017) does not require the assumption of bounded domain, as complexity depends and the solution x., denoted by 8o = ||xa x. ll. rather than the diameter Dx. We discuss the case without the bounded domain assumption in detail in Section 5.
hetween the initial point x
The TPGE method (Duchi et al., 2015) employs sequences stochastic finile difference, each with its smoothing parameter.
2.2. Randomized Smoothing
Based on Lemma 2.9, we define the stochastic finite differ- ence as follows
Randomized smoothing is widely used technique in zeroth- order optimization, which constructs a smooth surrogate of the objective function by applying perturbations along ran- dom directions (Duchi et al., 2012a; Gasnikov et al., 2022: Shamir, 2017; Yousefian et al., 2012; Nesterov & Spokoiny, 2017; Lin et al., 2022). In this work, we specifically focus on randomized smoothing based on the uniform distribution over the unit ball (Duchi et al., 2012a; Gasnikov al., 2022; Shamir, 2017). Formally, we define the smooth surrogate of the objective function fxx) as
& d -v: F v)v (2)
8(x,
2p
where E X. v,v~ U($ and & 5~ Under Assumption 2.7, the function evaluation F(x; {) returned by the stochastic zeroth-order oracle is an unbiased estima- tor of /xx). Consequently, the stochastic finite difference g( (x 14; v, {) is an unbiased estimator of fx(),, that is,
Eysu(s4 1), (0.6=_l(x,,/v..oo = fx)...
(x( - Eu-u + pu)),,
where j > 0 is the smoothing parameter. The following lemma establishes that the surrogate fx(x) preserves the convexity, and that the approximation error between fxx and (x) can be bounded in terms of μ (Shamir, 2017).
3. Parameter-Free Stochastic Zeroth-Order Optimization
We propose POEM, a parameter- free stochastic zgroth-order method, as described in Algorithm 1. POEM is built on the framework of projected SGD, following the iterative scheme
Lemma 2.8 (Shamir (2017, Lemma 8)). Under Assump- tions 2.5 and 2.6, the smooth surrogate fx(x) is convex and satisfies If (x) - (x)) < Lp all x E Rd.
X1+1 [x 17:8;),
(3)
The next lemma demonstrates that the surrogate f, is differentiable, regardless of whether fxx differentiable. Moreover, it shows that the gradient of (x( can be ex- pressed in the form of the finite difference.
where t/. > 0 denotes the step size, and the finite difference
gi e g(Xt, Me Ve, Ex)
(4)
Lemma 2.9 (Flaxman et al. (2004, Lemma 3.4)). For a continuous function| J R - IR, the gradient of its smooth surrogate fo is given by
is defined in equation (2), with the smoothing parameter Pr > 0. and random variables ~ U($d-1) and & ~ E.
(v))+ d (f(x + uv) - f(x-
We aim to make both the step size and the smoothing parameter 14, in equations (3) and (4) tuning-free, and still achieve near-optimal convergence rates. This is more chal- lenging than existing stochastic parameter- free first-order
(x) = EVWU(B--1)
- pvV)
2μ
where x E Rdd and p >
3

---

A Paramcter-Frec and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Algorithm 1 POEM
4. The Complexity Analysis
1: Input: Xo E X, Te E (0, Dxl, 221 1
In this section, we show that POEM (Algorithm 1) achieves near-optimal SZO complexity. The detailed proofs of the results presented here are provided in Appendix B.
2: f-1 = Te. G-1=0
3: for f- == =0...., - do
4: Ft = max (f-1, ||x xol1}
Our analysis focuses on the weighted average of the iterates generated by POEM, defined as
d
5: Mr FVV 1+1
Σ TKX
6:
U(S ). E1- ~
2i= Th k=0
d (F(x: + peVe: Et) F(x: (oVE;
7:
=
Since the objective function f is convex (Assumption 2.5), we apply Jensen's 's inequality to bound the optimality gap
2/x=
8:
G. = G + |lg:1?
9:
TK VGr
Pt
- f(x.)
1
Σ
Fx(f(xx)
-xxx)), (8)
=k=
Tk k=0
10:
X++1 = lxx - :7:::)
By combining inequality (8) with Lemma 2.8, we obtain
11: end for
f(x,) - fxx.)
12: Output: K,y where ty - arg max
1-1
1ST
F1
$
(xt) - Suc (x.) + 2L41s)
Ek=0 k== Tk k=
(9)
methods, which focus only on adapting the step size. In- spired by the strategy of DoG (lvgi et al., 2023a), we sched- ule the step size 17 based on the ratio between the distance from the initial point and the norm of the stochastic finite difference. Specifically, we define the cumulative squared gradient norm G2 A Ei-o [|ga 12 the distance to the initial point as rt A ||x; Xoll. and the maximum distance as Fr & maxkgi T re, where r. 0 denotes the initial movement, We define the step size at the (-th iteration as
Fa((VSpp (xx). xx) + 2Lp4k);
2k=0 k=0
where the last inequality follows from the convexity of fpu- We decompose the sum in the final line of equation (9) into
Fo Fg Xx - x.)
X
Σ 2LFu
weighted regret
noise SR.
from Akg. (10)
Ft
(5)
where A Vpr (xx) Bi- The regret term is a standard
VG
component in the complexity analysis of stochastic zeroth- order and first-order methods "Shalev-Shwarts 2012: Duchi et al., 2015; Balasubramanian & Ghadimi, 2018: Ivgi et al., 2023a). In the context of POEM, this term is scaled by the weights {Fx) 1--1 requiring careful control. The noise from gr arises from the discrepancy between the true gradi- ent ViS, and its unbiased estimator gs- The noise from l4 reflects the approximation error between the objective func- tion f and its smooth surrogate fFx- Notably, this noise doesn't appear in the analysis of first-order methods.
For initialization, we require the movement r. (0, Dx]- As we will show in Sections 4 and 6, the choice of r, influ- ences the theoretical convergence rates only by logarithmic term and has minimal impact on practical performance.
Moreover, we define the smoothing parameter as
(6)
1+1'
which is adaptive and generally larger than those used in existing stochastic zeroth-order methods (Nesterov & Spokoiny, 2017; Shamir, 2017; Duchi et al., 2015; Ghadimi & Lan, 2013; Duchi al., 2012b; Rando al., 2024). For example, Nesterov & Spokoiny (2017); Shamir (2017) set 14 (( in their analysis, depending the total it- eration budget T; Duchi et al. (2015) uses 14 (11 (di)) which may be quite small in high- digh-dimmnsional settings. Re- call that the smoothing parameter 14, appears in the denomi- nator of the stochastic finite difference in equation (2). Con- sequently, a larger ir improves numerical stability.
We now present upper bounds for the three components in equation (9): the weighted regret term, the noise from ga, and the noise from μi. To facilitate the analysis, we define
$1
|
xx||
and
S max 8k-
KSt
The following lemma provides an upper bound on the weighted regret for SGD-type iterations. Notably, this result holds independently of the specific form of the gradient estimator or the choice of step size, and thus applies directly to POEM (Algorithm 1).
4

---

A Paramcter-Frec and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Lemma 4.1 (Ivgi al. (2023a, Lemma 3.4)). For the itera- tion scheme (3), the weighted regret satisfies
Proposition 4.7. Under Assumptiios 2.5, 2.6 and 2.7, for any ó E (0,1) and t N4, POEM (Algorithm 1) satisfies
1-1 Σ
-(xx)-((x.) 160, (Ft+, Lod
(g X xx) ST F2 P2) VG---
Σx Fk/Fe
with probability at least 1 - 8, where 0,,5 11,5= 100 (og(1))))
To analyze the noise from gk we first establish upper bounds for gglll and its second moment 11
We then consider lower bound for Ex=o Rk/Fe. To this end, we introduce the following key lemma.
Lemma 4.2 (Shamir (2017, Lemma 10)). Under Assump- tion 2.6, POEM (Algorithm 1) satisfies
Lemma 4.8 (Ivgi et al. (2023a, Lemma 3.7)). Let 0n, a1 or be a positive non non-decreasing sequence, then
|g: || S Ld
and B||ls:11]s 5
ai 1 e (ar 11mmm-11)) 1):
(
T
max EST
where e is a numerical constant.
a
Remark 4.3. This lemma provides (d) upper bounds for both ||g:I| and [B[] |+1²), which are crucial for achieving optimal dependence on the dimension in the convergence rates. Unlike the original proof in Shamir (2017, Lemma 10), our analysis is based on the Euclidean norm and offers more concise argument by avoiding the use of fourth-order moments of the gradient estimator (see Appendix B.
where T E N
Since the sequence (Fr)T is positive and non-decreasing,
apply Lemma 4.8 with a, fz. This yields
Fk 2 Ω
T
max RST
Frr
log
(r//re)
(11)
k=
k==
Based on Lemma 4.2, we can provide an upper bound for the term A fT, (xx) g& /|- We then use concen- tration inequality for martingale differences (Howard et al., 2021: Ivgi et al., 2023b) to control the noise from gk.
where TT - arg maxi
Ei= Fk/Fe.
Before stating the main result, we define the probability space (Mn, Fo, P), where Kg denotes the sample space as- sociated with POEM (Algorithm 1) for given xo and r.. Fo is the sigma field generated by the random variable sequences {ve) and ( and P is a probability measure defined on Fo. Next, we define the event
Lemma 4.4. Under Assumptions 2.6 and 2.7, for any â E (0, 1), POEM (Algorithm 1) satisfies
P S : Σ FR( x.) 2 b1 58.
k=0
[-1
Ωg - w WEED So VI T,
Σ ( k Xx xx)
<be..
where we define b. - 181-181-11
/ Or. + 41.22222 1
and 02,8 - log(60 log(Gt/
By Lemma 4.4, given 8 E (0, we have P(2s) 2 1 8. We then define the sigma field F; & (A A c 2g n Fo. which satisfies Fs C Fo. Furthermore, the Lipschitz con- tinuity of f and the boundedness of the domain X', ensure that () - f(xx)] < LDx < cc. Therefore, the con- ditional expectation [[f((,,) ) - fxx.) [Fo] exists and is
Next, we provide an upper bound for the noise from pkc Lemma 4.5. POEM (Algorithu 1) satisfies
1-1 Σ
2Lran S ALF ALRI-IVdl
unique (Durrett, 2019, Chapter 4.1).
k=0
By combining Lemma 4.2, Proposition 4.7, and equa- tion (11), we arrive at the main result.
where log,() (-) A log(.) 1.
Theorem 4.9. Under Assumptions 2.1, 2.5, 2.6, and 2.7, for any 8 E (0, 1) and T E N4,, POEM (Algorithm 1) initialized with Xo E X and r. E (0, Dx] satisfies
Remark 4.6. The choice of the smoothing parameter in (6) implies that # = ((//kk)) Using this expression, we can bound the series by approximating it with an integral, which leads to the stated result in Lemma 4.5, A detailed proof is provided in Appendix B.3.
(X - f(x.) d
so
(
Vd
Dx
)):
LLDx log, Te
By combining Lemmas 4. 1, 4.4, and 4.5 with equations (9) and (10), we obtain the following upper bound on the opti- mality function value gap.
vT
with probabiliyy at least 1 155, where 0r, (og(60)og(677/8))
5

---

A Carameter-Frec and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
By suppressing the logarithmic factors using the (-) nota- tion, the SZO complexity for finding conditionally expected e-suboptimal solution with probability at least - 8 is
We now provide the complexity analysis for the modified POEM. Unlike in the bounded domain setting, the quan- tity Fr cannot be simply controlled via Dx. Instead, our goal is to show that F. = (su), which implies that X2 re- mains close to both X and x,. Starting from the iteration update X = 11x (Xx - M.gg)), we obtain the incquality
aI. D3 Ô
2²
The SZO complexity established in Theorem 4.9 matches the lower bound for stochastic zeroth-order optimization established by Duchi et al. (2015).
|x++1 - x,12 S X X.
Rewriting this inequality using the definition of Sy in Sec- tion 3. we have
Remark 4.10. As 5 0, S2g - Gg in probability and F8 approaches Fo. which implies (x, - f(x.) Fs) ap- proaches E[f(87) fx.) [oo = f(xrz) (xx).
6 - 5x 1 1x11 112 + 21/ (As, Xx: - x+)
- -1 (V V.Lu (xx), Xx= - -x.)
5. Results for Unbounded Domains
where A k:
-[pn (xx) gk- Summing the above inequal- ity over k= 0, ,,.,... 1
1, we obtain
In this section, we extend our method address the stochas- tic convex optimization problem in settings where the do- main may be unbounded. To accommodate this, we relax Assumption 2.1 as follows.
1-1
1-1
2
2
<
mc gk
2
1| 2
Σ
mh (A: Xx- - -x,)
k=0
k=
(14)
Assumption 5.1. The domain X' S Rd is closed and convex. Moreover, there exists a point x, E X' such that f(xx)) = minxex (x).
2
The (V (xx). xx)
k==
Therefore, we can upper bound F; by controlling each of the three terms on the right-hand side of inequality (14). Note that the last term in equation (14) does not appear in the analysis of first-order methods like DoG (Ivgi et al., 2023a). Following the analysis in Appendix C.1, we establish the follow upper bound for Ft.
Remark 5.2. In our analysis for the bounded domain (The- orem 4.9), the upper bound on (x,,,,,) fxx)) F&] in- cludes the term (Dx ever, this term may become invalid after relaxing Assump- tion 2.1 to Assumption 5.1, as Dx could be infinite.
where r. E (0, Dx)) How-
In the remainder of this section, we first modify POEM by introducing an overestimate of the Lipschitz constant L to address the problem without assuming a bounded do- main. We then show that such estimation is unavoidable in the unbounded setting. The detailed proofs for the results presented in this section are deferred to Appendix C.
Proposition 5.3. For any 8 E (0, POEM (Algorithm 1), with settings т)- Fe/V/G, Pt dr:/(t + 1)?, and r. (0, 380), satisfies (Pr > 3sp) 6.
We consider the probability space (Ωo, Fo. TP), where Ωn is the sample space of the Algorithm I under the modified set- tings used in Proposition 5.3, Fo is the sigma field generated by the random sequences {vo) T- and (E probability measure defined on Fo-
We introduce the quantity
17-1 and is a
G2 A 8'0,, log² (t + (), + 1607, sd (12)
Following the settings of Proposition 5.3, we define the set
where fr.s log log (6T/ G. = Ei 11 as defined in Section 3 and T. is an overestimate of the Lipschitz constant L such that L > L.
T-1
Ôg a w E i. ST T,
i Ax. Σ A=
k xx xx+) S 2 s
For the unbounded domain, we modify POEM (Algorithm 1) by updating the step size and smoothing parameter as
where 7 2 m II(t < () and Ç a min(te E EN| Ft > 350
Fr VG
dr.
The derivation of Proposition 5.3 (see Appendix C.I) shows that if r. 380, then Fr Σ 3sp for all w E Ω2z. Moreover, it holds that (().)) 2 1 - 8.
1/:
and
(t 1)
(13)
where r -|x Xu| || and F. = maxkgt Pk V re, following the notation in Section 3. We also define G_1 0 for equation (12) when t = O. Note that the parameters T and 6 only influence the logarithmic factor in G.. Furthermore, the term 160r, [2 in equation (12) becomes relatively insignificant compared to G.-1 1 as grows large.
Similar to Proposition 4.7, we can establish an upper bound on the optimality gap for the unbounded setting as follows (see Appendix C.2 for the proof).
Proposition 5.4. Under Assumptions 2.5, 2.6 and 2.7. for any 5 E (0, 1), POEM (Algorithm 1) with the modified
6

---

A Faraecter-Frec and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
settings from Proposition 5.3 satisfies
parameter-free zeroth-order algorithm for stochastic con- vex optimization without bounded domain assumption is provably unattainable.
-(x)) f(x.) - 200,, + +0){ G/- Ld)
(15)
Ei FF/Fe
We assume that the stochastic zeroth-order algorithm A accepts valid estimates T., L, and such that L S L S and 2 80 I 8. Based on this setup, we establish the following lower bound on the function value gap for the stochastic convex optimization problem.
with probability at least 1 where 01,0 -la=-logh (og(())))))
Following the settings of Proposition 5.4, we define the set
G A {wEES Ao : ST
Theorem 5.6. Let 0 TR.22 - Th. be any polylogarithmic function, let d E N, and ler A be stochastic zeroth-order algorithm satisfying Assumption 2.7, with valid estimates L. L. 8, and 8. Then, there exists an L-Lipschitz convex function f R. - such that, for any initial point x E R and any number of SZO calls T Z 2, the algorithm A returns point & satisfying
Σ Fu Xk x.) be
where be = 15 1 +
4L2d=02 The proof of Proposition 5.4 shows that inequality (15) holds for all w E Lig. Moreover, we have P({2)) 2 5
Or.
Next, we define Fs _ (A A Ω2 n n Fo. which sub-sigma-fiell of Fo- Since the probability space is conclude the conditional expectation (xx(x,,) (xx) Fxs exists and is unique, even if the domain Dx is unbounded. (Please see Appendix C.3 for the detailed derivation.)
L (
Vd vT
f.
(
..d)
L's
constructed for an algorithm with finite T,
with probability at least 1/c.
Remark 5.7. In a recent work, Khaled & Jin (2024) showed the impossibility of an ideal parameter-free algorithm for stochastic first-order optimization by constructing hard instance in the one-dimensional setting. In contrast, the lower bound for zeroth-order optimization established in Theorem 5.6 must additionally consider the dependence on the dimension of the problem, highlighting key distinction from the first-order case.
We now combine Propositions 5.3 and 5.4 to establish a convergence result without a bounded domain assumption.
Theorem 5.5. Under Assumptions 2.5, 2.6, 2.7, and 5. for any 8 E (0, 1/2). POEM (Algorithm 1) with the modified settings used in Proposition 5.3, satisfies
[[)((,,)) - -(xx) [Fs]
6. Numerical Experiments
5o d(
VdL
Or7,880 log+
T
VT
This section presents numerical experiments to evaluate the empirical performance of POEM (Algorithm 1). We consider a stochastic optimization problem of the form
with probability at least 1 1- 28, where so
||x0 x.|| and
a log, (T + 11 1o 16g (8)))
min f(x) - (aab))) (x;
XEX
By setting L L, the upper bound on the conditional expectation shown in Theorem 5.5 simplifies to
where F(x; a. = max (0, ba bx. (a, b) ER x (+1} is uniformly sampled from a binary classification dataset ((a,, b,)) The feasible set is defined as X' {x E Rd ||||| R] with radius R = 1. We conduct experiments benchmark datasets from (Chang & Lin, 2011), includ- ing "mushrooms" (d 112, n = 32, 561), and "w8a" (d = 300, n = 49, 749). For com- parison, we consider two stochastic zeroth-order algorithms: Two-Point Gradient Estimates (TPGE) method (Duchi et al., 2015) and Two-Point Bandit Convex Optimization (TPBCO) method (Shamir, 2017).
o((
+
Vdl VT at oT sLg log
$00 re
This yields the SZO complexity of O(dL's for find- ing an e-suboptimal solution &,y, which improves upon the T.2 //2)) complexity established by Nesterov & Spokoiny (2017).
8124). "a9a" (d = 123,
However, the settings in Theorem 5.5 (also Proposition 5.3) require that r. E (0, 3so] where so ||x0 x.|| || is un- known in practice. Furthermore, the first term in the upper bound of Theorem 5.5 depends linearly on T.. Ideally, we would like to design an algorithm that achieves an SZO complexity close to O(dL2 s2/c2,, with only logarithmic dependence on uncertain problem parameters such as re and T.. Unfortunately, we show that such an ideal, fully
Figure shows the comparison of SZO complexity ver- sus function values. For POEM, the initial movement is set to r. = 1 Baseline methods are evaluated under two configurations: theoretical parameter settings (TPGE-T, TPBCO-T), and well-tuned step sizes (TPGE-E, TPBCO- E). Results demonstrate that POEM converges faster than
7

---

A Paramcter-Frec and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
1.0
TPGE-T
1.0
1.0
TPGE-T
TPGEE
TPGE TPSCO-T
TPGE-E TPSCO-1
Function Value
TPSCO-1
0.9
TPBCO-E
TPSCO-E
0.8
TPSCO-E
POEM
Loss
0.6
0.7-
0.4
0.6
0.2
1000
2000
3000
4000
5000
500
1000
1500
2000
0
20000
40000
60000
80000
100000
Complexity
Complexity
SZO Complexity
(a) mushrooms
(b) a9a
(c) w8a
Figure 1. The comparison the SZO complexity versus the function value during the iterations.
1.0
1.0
1.0
Last Function Value
Last Function Value
Last Function Value
0.8
0.8
0.6
0.4
POEM
R-1
0.6
POEM
R-1
0.6
POEM
R+1
0.4-
10
10
10
10"
10
10
10
10
10
10"
10"
(a) mushrooms
(b) a9a
(c) w8a
Figure The comparison on the parameter settings (r, POEM and 1/L for other methods) against ((x)).
10
10
10"
Step Sizan
Step
80
Step
10
10"
10"
10'
10"
10"
(a) mushrooms
(b) a9a
(c) w8a
Figure
The change of step size with difference r. for POEM.
TPGE-T and TPBCO-T, while its performance is compara- ble to the well-tuned variants (TPGE-E, TPBCO-E).
7. Conclusion
In this paper, we propose POEM, a novel zeroth-order op- timization algorithm for stochastic convex optimization. It can dynamically schedule both the step size and the smoothing parameter during iterations. We show that POEM achieves near-optimal stochastic zeroth-order oracle com- plexity for problems with bounded domains. Notably, its initialization only impacts convergence rates by logarith- mic factor. We further extend POEM unbounded do- mains and derive lower bound, which reveals that an ideal parameter-free algorithm impossible in such settings. We also conduct numerical experiments to confirm the practical efficiency of POEM.
We further study the practical impact of parameter settings. Specifically, we present the objective function value the fi- nal iteration (T' 10%) across all algorithms under different configurations. Figure 2 summarizes these results, where tune the initial movement r. in POEM and the term 1/L in baseline methods over the range (10-7, ...,..., 102). is clear that POEM exhibits greater stability across param- eter settings compared to baseline methods. More impor- tantly, when r. < R = 1, the choice of Te has negligible impact on the function value. This supports our theoretical analysis (Theorem 4.9), where r. only influences the loga- rithmic term in the complexity bound if it does not exceed the domain diameter. Additionally, we track the evolution of step sizes in POEM under varying Te. As shown in Fig- ure 2, the step sizes converge to similar values across all configurations, highlighting the algorithm's 's adaptive nature.
In future work, we are interested in extending the ideas of POEM to broader applications, including zeroth-order optimization for minimax and bilevel problems. Another promising direction is the development of parameter-free zeroth-order methods for finite-sum optimization.
8

---

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Acknowledgements
Cutkosky, A. and Orabona, F. Black-box reductions for parameter-free online learning in banach spaces. In Con- ference On Learning Theory, pp. 1493-1529, 2018.
This work supported by the National Natural Science Foundation of China (No. 62206058), the Major Key Project of PCL under Grant PCL2024A06, and Shanghai Basic Research Program (23JC1401000).
Defazio, A. and Mishchenko, K. Learning-rat--free learning by D-adaptation. In International Conference on Machine Learning, pp. 7449-7479, 2023.
Impact Statement
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12661):2121-2159, 2011.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Duchi, J. C., Bartlett, P. L., and Wainwright, M. J. Ran- domized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012a.
References
Agarwal, A., Dekel, O., and Xiao, L. Optimal algorithms for online convex optimization with multi-poin poitt--pintttie bandit feedback. In Conference Learning Theory, pp. 28 28-40, 2010.
Duchi, J. C., Jordan, M. I., Wainwright, M. and Wibisono, A. Finite sample convergence rates of zero-order stochas- tic optimization methods. Advances in Neural Informa- tion Processing Systems, pp. 1439-1447, 2012b.
Balasubramanian, K. and Ghadimi, S. Zeroth-order (non)- convex stochastic optimization via conditional gradient and gradient updates. In Advances Neural Information Processing Systems, pp. 3459-3468, 2018.
Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61) 2806, 2015.
Barzilai, J. and Borwein, M. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1):141- 148, 1988.
Durrett, R. Probability: theory and examples, volume 49,
Cambridge university press, 2019.
Bernstein, J., Vahdat, A., Yue, Y., and Liu, M.-Y. Y. On the distance between two neural networks and the stability of learning. Advances in Neural Information Processing Systems, pp. 21370-21381, 2020.
Flaxman, A. D., Kalai, A. T., and McMahan, H. B. Online convex optimization in the bandit setting: gradient de- scent without a gradient. In ACM-SIAM Symposium on Discrete Algorithms, pp. 385-394, 2004.
Berrada, L., Zisserman, A., and Kumar, M. Training neural networks for and by interpolation. In International conference on machine learning, pp. 799-809, 2020.
Gasnikov, A., Novitskii, A., Novitskii, V., Abdukhakimov, F., Kamzolov, D., Beznosikov, A., Takáč, M., Dvurechen- sky, P., and Gu, B. The power of first-order smooth opti- mization for black-box non-smooth problems. Interna- tional Conference on Machine Learning, pp. 7241-7265, 2022.
Bhaskara, A., Cutkosky, A., Kumar, R., and Purohit, M. Online learning with imperfect hints. In International Conference on Machine Learning, pp. 822-831, 2020.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
Carmon, Y. and Hinder, O. Making SGD parameter-free. In Conference on Learning Theory, pp. 2360-2389, 2022.
Chang, C.-C. and Lin, C.-J. LIBSVM: a library for sup- port vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):1-27, 2011.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explain- ing and harnessing adversarial examples. arXiv preprint arXiv: 1412.6572, 2014.
Chen, K., Langford, J., and Orabona, F. Better parameter- free stochastic optimization with ODE updates for coin- betting. In AAAI Conference on Artificial Intelligence, pp. 6239 6239-6227, 2022.
Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J.
Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055 1080. 2021.
Chen, L., Xu, J., and Luo, L. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. In International Conference on Machine Learning, pp. 5219- 5233, 2023.
Ilyas, A., Engstrom, L., and Madry, A. Prior convictions: Black-box adversarial attacks with bandits and priors. arXiv preprint /80700778 2018.

---

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Ivgi, M., Hinder, O., and Carmon, Y. Dog is SGD's best friend: A parameter-free dynamic step size schedule. In International Conference Machine Learning, pp. 14465-14499) 2023a.
Mania, H., Guy, A., and Recht, B. Simple random search provides competitive approach reinforcement learn- ing. In Advanced in Neural Information Processing Sys- tems, pp. 1805 1814, 2018.
Ivgi, M., Hinder, O., and Carmon, Y. Dog is SGD's best friend: A parameter- free dynamic step size schedule. arXiv preprint arXiv:2402.07799, 2023b.
Mhammedi, Z. and Koolen, W. M. Lipschitz and comparator adaptivity in online learning. In Con- ference on Learning Theory, pp. 2858-2888 2020.
Jacobsen, and Cutkosky, A. Parameter-fiee mirror de- scent. In Conference on Learning Theory, pp. 4160-4211, 2022.
Nazari, P., Tarzanagh, D. A., and Michailidis, G. Adap- tive first-and zeroth-order methods for weakly con- vex stochastic optimization problems. arXiv preprint arXiv:2005.09261 2020.
Khaled, A. and Jin, C. Tuning-free stochastic optimization. In International Conference on Machine Learning, pp. 23622-23661, 2024.
Nesterov, Y. and Spokoiny, V. Random gradient-free mini- mization of convex functions. Foundations of Computa- tional Mathematics, 17(2):527-566, 2017.
Kiefer, J. and Wolfowitz, J. Stochastic estimation of the maximum of regression function. The Annals of Mathe- matical Statistics, pp. 462-466, 1952.
Orabona, F. and Pál, D. Coin betting and parameter-fiee online learning. In Advances in Neural Information Pro- cessing Systems, pp. 577-585, 2016.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference Learning Representations, 2014.
Orabona, and Tommasi, T. Training deep networks with- out learning rates through coin betting. In Advances in Neural Information Processing Systems, pp. 2157-2167, 2017.
Kornowski, G. and Shamir, O. An algorithm with optimal demennioon-deeendence for zero-order nonsmooth noncon- vex stochastic optimization. Journal of Machine Learning Research, 25(122):1 -14, 2024.
Paquette, C. and Scheinberg, K. A stochastic line search method with expected complexity analysis. SIAM Journal Optimization. 30(1):349-376) 2020.
Lan, G., Ouyang, Y., and Zhang, Z. Optimal and parameter- free gradient minimization methods for smooth optimiza- tion. arXiv preprint arXiv:2310. /2139, 2023.
Polyak, B. Introduction to optimization. New York,
Optimization Software,, 1987.
Rando, M., Molinari, C., Rosasco, L., and Villa, S. An op- timal structured zeroth-order algorithm for non-smooth optimization. In Advances in Neural Information Pro- cessing Systems, pp. 36738-36767, 2024.
Li, T. and Lan, G. A simple uniformly optimal method with- out line search for convex optimization. arXiv preprint arXiv:2310.10082 2023.
Lin, T., Zheng, 7., and Jordan, M. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex opti- mization. In Advances in Neural Information Processing Systems, pp. (6160-26175 2022.
Rolinek, M. and Martius, G. L4: Practical loss-based step- size adaptation for deep learning. In Advances Neural Information Processing Systems, pp. 6434-6444, 2018.
Shaham, U., Yamada, Y., and Negahban, S. Understanding adversarial training: Increasing local stability of super- vised models through robust optimization. Neurocomput- ing, 307:195-2044 2018.
Liu, Y., Chen, X., Liu, C., and Song, D. Delving into transferable adversarial examples and black-box attacks. In International Conference on Learning Representations, 2016.
Shalev-Shwartz, S. Online learning and online convex opti- mization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
Loizou, N., Vaswani, S., Laradji, I. H., and Lacoste-Julien, S. Stochastic Polyak step-size for SGD: An adaptive learn- ing rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pp. 1306-1314, 2021.
Shamir, O. An optimal algorithm for bandit and zero-order
convex optimization with two-point feedback. Journal of Machine Learning Research. 18(52):1-1,, 2017.
Luo, H. and Schapire, R. E. Achieving all with no param- eters: AdaNormalHedge. In Conference on Learning Theory, pp. 1286-1304, 2015.
Shazeer, N. and Stern, M. Adafactor: Adaptive learning rates with sublinear memory cost. International Con- ference on Machine Learning, pp. 4596 3596-4604, 2018
10

---

A Faraecter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Streeter, M. and McMahan, H. B. No-regret algorithms for unconstrained online convex optimization. In Advances in Neural Information Processing Systems, pp. 2402-2410, 2012.
Tan, C., Ma, S., Dai, Y.-H,, and Qian, Y. Marzilai-Borwert step size for stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 685-693, 2016.
Tieleman, Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26, 2012.
Vaswani, S., Mishkin, A., Laradji, I., Schmidt, M., Gidel, G., and Lacoste-Juliee S. Painless stochastic gradient: Inter- polation, line-search, and convergence rates. Advances in Neural Information Processing Systems, pp. 3732-3745 2019.
Wang, B., Zhang, Y., Zhang, H., Meng, Q., Sun, R., Ma, Z.-M., Liu, T.-Y., Luo, Z.-Q., and Chen, W. Provable adaptivity of Adam under non-uniform smoothness. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2960-2969, 2024.
Wang, X., Johansson, M., and Zhang. T. Generalized Polyak step size for first order optimization with momentum. In International Conference Machine Learning, pp. 2023.
You, Y., Gitman, I., and Ginsburg, B. Large batch training of convolutional networks. arXiv preprint 1XX8:17708.3880 2017.
Yousefian, F., Nedić, A., and Shanbhag, U. On stochas- tic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1 48(1):56-67, 2012.
Zeiler, M. D. ADADELTA: an adaptive learning rate method. arXiv preprint 02 2012.
Zhang, Y., Chen, C., Li, 7.,, Ding, T., Wu, C., Ye, Y., Luo, Z.-Q., and Sun, R. Adam-mini: Use fewer learning rates to gain more. In International Conference on Learning Representations, 2025.

---

A Parameter-Free Freet and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
A. Some Basic Results
first present some basic lemmas.
Lemma A.1 (Shamir (2017, Lemma 9)), Suppose ~ U(S Then, for any function h: R - R hat is L-Lipschitz with respect to the f--norm, the following concentration inequality holds
cdt2 T,2
P((((v) - ((S-- 2 2) S 2exp
where is numerical constant.
Lemma A.2 (Ivgi al. (2023a, Lemma D.2)). Let S be the set of non-negative and non-decreasing sequences. Let c. and let X₁ be martingale difference sequence adapted to Fi such that [X,] $ with probability for all t. Then, for all ó E (0, 1) and X, Fi-1 such that Xel S e with probability I,
[-1
P 3l ST (m ES:
Σ k=0
yk x
b
S 8,
where by _ 8y1 Vo.s ( x
+ 228 and 0,, a log(60
Lemma A.3 (lvgi et al. (2023a, Lemma C.3)). Let a- au ....a a be nondecreasing sequence of nonnegative numbers, then the following inequality holds
Gk ak-1
S
log (ax/a_1)
Lemma A.4 (Carmon Hinder (2022, Corollary 1)), Let > and X, be a martingale difference sequence adapted to F, such that [X,] S with probubility for all I. Then, for all (0,1), and X, E Fi-1 such that [Xe] S a with probubility the following inequality holds
BIS:
Σ km
X
> 4 4
0,,5
km/
B. The Proofs for Section 4
We provide detailed proofs for the results under the bounded domain assumption.
B.1. Proof of Lemma 4.2
Proof of Lemma 4.2. For convenience, we omit the subscripts. Recall that the gradient estimator g is defined
d (F(x + vv: F(x E)), where U((d-1).
g(x,n,V,E) 24
By Assumption 2.6, the function F(x; {) is almost surely L-Lispchitz in x. Thus, have
d F( + uv: E) F(x pv: e)llvl & 2d|vv|2 Ld,
Ig||
24
where the last equality follows from the fact that |||| 1.
Next, using the definition of and ||v|| 1 again, we compute the second moment of g as
d2 EE-uys
E Ey- 1 ||]||||1]
(I[Uux vv; F(x - vv; {))
2
12

---

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
For any a E R, we can rewrite this
df E. uv: - -a) aa- -FF(x vv: a])²].
Ev- 1)[l||!
41²
Applying the inequality (a b)2 < 2n 2b?, obtain
d?
Ev 1 و || 1
(Bv 1y) uv: aa) Ev- 1)((F(X -v:
241²
Since the distribution U(Bx-1) is symmetric about the origin, the on the right-hand side are equal. Thus,
dc Ev-orge-))(F( vv: aa²1.
(16)
Let h(v) & F(x + gv; Since F(x; E) L-Lispchitz in x, it follows that h(v) is pL-Lipschitz in v. By Lemma A.1, the variance of h(v) bounded as follows
E Ev s)((h(v) EE 1)[h(v)])² P((h(v) EV ,,[h(v]]) t) dt
P((h(v) Ev-Wig 1y[h(v)] vt) dt
$ exp (- cdt
2
L3
p2
dt
cd
where e > O is numerical constant. The first equality follows from the identity (Durrett, 2019, Lemma 2.2.13), which states that if random variable Y almost surely, then
E| [
P(Y y) dy.
Setting Byw-(ge-i,(hh()) [y[[v)] and combining the variance bound above with the inequality (16), we have
(o=0084-1)[18813] < d²
222 (v-uuser,((((()) - -Ew-orae- [[(v)) < Iddd.
Finally, we apply the law of total expectation to derive ]| EE || ||] S 2L'
B.2. Proof of Lemma 4.4
Proof of Lemma 4.4. We begin by defining the filtration Fx & E., 2is0iii k) for k E N and F-1 - (0,2). Next, we introduce two stochastic processes (X2, & E N) and (& E N) defined as
1
Xx
Ar. Xx: x.) Fr and X2
V (xx), x.) E Fx-11
(17)
Sk
54
where A
V. (xx) gk. Thus, derive that (X2, l E N) is adapted to (Fx, k N) and (&g, k E N) is predictable with respect to (FR, N). Moreover, since Be an unbiased estimator of V f. (xx) conditioned on F have
E[Xx F
E(V (xx) gk. X x.) F = 0,
5k
where we use the fact that 8s E FR-1- This implies that (Xx, fe k E N) forms martingale difference process. Next, applying Lemma 4.2, know that ||gull L.d. Since Ex is unbiased estimator of V V (xx), obtain
|V Sug (xx)l
|[ [gx]]l < Ev, [lgg
Ld.
13

---

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
follows that
| S gk + V (x+)ll - 2Ld.
From equation (17), we immediately have X& A S 2T. and | S Vpn (x+) & Ld.
Now, define the sequence Y == Sk for E N, which non non-negative and non-decreasing. Using the concentration inequality for martingale difference sequences from Lemma A.2, and letting E (0, 1) and c 2Ld, we obtain
Σ Yu-Ke ) k=
PP 3
< :
Σ
Fk x. - x.) 2b = 3E T: k=0
3 s T. (y ES:
Σ yk
2 by
where b, & 15 / 4L2003 00s & log(60log(6t/0)) and S is the set of non-negative and non-
decreasing sequences.
B.3. Proof of Lemma 4.5
Proof of Lemma 4.5. Define the partial S E. 1/v fort N+. An upper bound for St can be obtained via the following integral
St S 1 '"
dx 2 - 13 2VF.
V
Using this bound, together with the definition of Po in equation (6), we can bound the noise as follows
Σ K=0
2Trx 2T
Σ ih 2LVv P =4T=2- dt.
k=0
B.4. Proof Proposition 4.7
Proof of Proposition 4.7. Combining Lemma 4.1, 4.4 and 4.5 with equations (9) and (10), we obtain that, with probability least 1 6, the upper bound for fxx:) - fxx.) given by
(25, + G + 85, 10, 0 4
4F.LVdd
Σ1=0 Fk/Fe
where we use the fact that Fz-1 S Ft and 5; S 8t. Applying the inequality v + <a to the bound, we have
(23, + Fr) Ft) G 85, ( 2d, + 4F,L
Σ Fz/FF
Finally, using the triangle inequality 8, S Ft + sp, we obtain the bound
0,, + so)( Gi-1 Ld L
16
Σ Fk/Fs
14

---

A Paramcter-Frec and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
B.5. Proof of Theorem 4.9
We begin by introducing several useful properties of conditional expectations.
Lemma B.1. Let (2, Fo, IP) be a probability space, and let X1, X2 be two random variables defined on it. Suppose F Fo sub-o-algebra, and El. [F] denotes the corresponding conditional expectation. If X1 X2 on a set B E F, then E| F - _[X2| F] almost surely on B.
Proof of Lemma B.I. We follow the proof strategy of Durrett (2019, Theorem 4.1.2). For any > 0, define the event A = (w E Q E| F 2 F 2 e), which satisfies A E F since both conditional expectations are F-measurable. Because F, their intersection n B E F. Then, by the definition of conditional expectation, we have
J AnB
f
FX2 FP
X1 21-x2c0 dP 20
JACB
where the inequality follows from the assumption X X2 on B. On the other hand, by the definition of A, we have
E
dP
PPAnnB.
AnB
AnB
Combining the two inequality, have P(An B) 0, which implies that
P(w B E X1
E[X₂ F
Since this holds for all 6 > 0, it follows that E |F] S E 22 F almost surely on B.
Lemma B.2 (Durrett (2019, Theorem 4.1.13)). Fo C F. then E Fol Lemma B.3 (Durrett (2019, Theorem 4.1.10)). Let be convex function and X be a random variable such that E|X < 00 and (X)) co.
E| F
Fol.
Then,
6(E < x E(((
We are now ready to prove Theorem 4.9.
Proof of Theorem 4.9, Recall the event
- 2
Σ X - x.)
< <be -x.)
Fo.
which satisfies P(Rs)) 2 1 - 8 by Lemma 4.4. From Proposition 4.7, we know that for any E Us and all / S T, the
following inequalty holds
f(x)) - f(x.) s 16. 0,.(FF + (u)(V Ld Lvdt)
E Fk/Ft
Combining this with equation (11), obtain that for all Ωs.
- co 6fr + so) G + Ld + L drr
Fry
log.
T
where is constant and TT = arg mT Et- Fk/Fe. Since 02,5, Fr, and G. are non-decreasing in f and Tr S T, we can simplify the bound
0r.(Fr + s0)(GrT- Ld L
f(x,) -f(x)xx== S..
log+
FT
re
15

---

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Noting that the diameter is Dx and r. S Dx. have FT Dx. Substituting this into the above bound yields
f(x,,) - f(x.) S 20g Dr Dr.DD(VGTTo /T-1 + Ld LV
Dx
log+
Te
Recall that F8 - (A: A (6) Fo is sigma field satisfying F& C Fu. Moreover, we have U2g B.I, obtain that for any S2g.
Fs. Applying Lemma
[l f(x.)(())))) f(x.) S 2cg 0r, GT F3) Id+ LVdT
Dx
log
(18)
Tr
Next, we bound the conditional expectation of Gr-1 using Lemma 4.2 and Lemma B.2 as follows
T-1
B [Fs] TB
Σ
|
cT.
Since the square root function is concave, applying Jensen's 's inequality (Lemma B.3) gives
B B[vGr-i FF) S VE[Gr-11 Fs) S LValT.
Substituting this back into equation (18), conclude that for any w E 2sg the following inequality holds
d T
Vd
0r Sr )
Dx
[l f(x.) Fsl ci
+
log+
(19)
VT
re
where ej constant. This implies that the upper bound (19) holds with probability at least
C. The Proofs for Section 5
We provide detailed proof's for the results without assuming a bounded domain.
C.1. Proof of Proposition 5.3
For simplicity, we define the following stopping time
< f min(l E Fz > 350}-
Using this stopping time, define modified step size
in 2 m I(t < C)2
where the indicator function Il(t <) equals 1 if (, and otherwise.
Before proving the proposition, first present and prove several supporting lemmas. Lemma C.1. Let T E N+. For any I S T, the following inequality holds
l
<
2
Proof of Lemma C.I. By the definition of ÿt and using the identity ||g = IGG - Gk- we can bound the sum as follows
c-1
R Gk-1)
G G
Pel
12
The
g
|g
G₁
2
6-1
(20)
k=0
where we G_1 O. We use lower bound for G²₁y
(k 1)
Gb + di
G₁ 2 800 222 log?
2 280rr,6r + +dT
d
d2
16

---

A Fereactte--Fre and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
where the last inequality follows from Bxll S Ld (See Lemma 4.2). Substituting this bound into (20), we obtain
- Gk-Gk-1
1 986
(21)
8 km (GL + 1o2
C2+d d2
8 ,
800
2
The second inequality holds by applying Lemma A.3 with dR- Gk + cLLL2.
Lemma C.2. For any d E (0, 1), the following inequality holds
1-1
31 S ST:TT:
Σ
i (A X - Xx) > > So,
Proof of Lemma C.2. We consider the filtration Fx = ovvi, Es. 0 S S k) for ho E N and F-1 = (0) as defined in
Appendix B.2. Note that 7 E Fk-1. Define the stochastic processes (Zz, k E N) and (Ze, k E N) as
Z ū [Ax,x, X - -x.) Fx and 2x = nu Juu (xx) x - xx) E Fk-1.
where A Spp (xx) gk. By construction, we have
E E|Z Fa-1] = nn BB fug (xx) gk, - -x.) [k-1] = 0, where k E N.
Thus, (Zx, FR, k E N) is a martingale difference process.
We now bound |Zx] Using the fact that 8 S Fz + So, we obtain
FC- T5-18c-1lIA
12s A
Z S Sk S
VGK
VGk
From Appendix B.2, we have | S 2L. Moreover, we have G₁ 2
16 8 800 of L Therefore, we conclude
6s9
7 <
820
The same upper bound also applies to /2/l. Now apply Lemma A.4 with = 6sz/ This gives
t-1
PP
T
Σ
Za > 4
0,,8
E(2. 2a)2 + c203, 5..
(22)
K=
k=0
The upper bound for Et-b - ) is given by
12 sg
Σ - (2.22,)2 2+)²= ((x,, xx,)²² <
Σ nell 12 (4so)²
Σ
n gg 2
840
km
km 0
km 0
(23)
where the third inequality follows from 5k I F + su and the last follows from (21). Substituting (23) into (22), we get
1-1
122
62
122 84
6 4
00.8 Σ
7xx 22 + 203 11 02.6
02
4v
810
1,0 85
84
k=
Thus, we have
P T
Σ
( xx)
-xi)
> >5²)
58.
k=U
17

---

A Paramcter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Lemma C.3. Let T E N+. For any & S T, the following inequality holds
Th (V (xx), - -xx) - $6
4
Proof of Lemma C.3. By Lemma 2.8, we have
(Wen (xx), x, xx) S fax (x.) - su (xxx) SS f(x.) - f(xx) + 21μr S 2
where the last inequality follows from the fact that f(x,) infxex (xx.. Thus, the summation can be bounded as follows
min(g-1,t)
min(s-1.h 1,8)
Σ
i (V (xx), X, - xxx)
ne (xt), - xx) S 2L
TlaKk-
k=0
Given that lA = dix/(K (I: + 1)2 and G% 2 16. 8 ,, follows that
min(g-11)
72 min((-1,t)
M (xa, -xx) 4 L
2L
5-1
1
3x s
+ 1)2
2 82
(k: (k+ 1)2
82
k=
k=
where the third inequality uses the fact that Σx= 1/h² n² /6 and Fç-1 3sg-
Based on Lemmas C.1, C.2, and C.3, we now establish Proposition 5.3. Proof of Proposition 5.3. Fix any d >> 0, and define the event
Ôg a { wE
Tweeo: Qo Vt < T,
Σ nu (A. - x.) S 2 k=
By Lemma C.2, it holds that P({ss) 2 5.
We now proceed by induction on / to show that F. < 380 for all / < T and any E Ωz. For the base case, we have
To Te S 3sg. For the induction step, we assume Fi-1 S 3sp. which implies that Ç > - 1. From equation (14), we have
1-1
$0
+
+2
me (A. Xx - xx) +2 +
mc (V fu (xx), - xxx)
k=0
k=0
vi gg 1| +
m (A X2 xx,) +
(x))) (x+), - -x)).
R=
k=0
k=0
where the equality holds since ( > l Now, applying Lemmas C.I, C.2, and C.3, we obtain for any Яg
1 5² - - 56 25 +
56 3
which implies that st S 25g. Hence, we have r. S st + for all < T for any S2g. Equivalently, we have P(rr > 3sp) < 6.
50 3sp. By induction, it follows that F. max(Fr-1,7t) S 3s0
C.2. Proof of Proposition 5.4
Proof of Proposition 5.4. Since G² 2 Gr, we can apply the result of Ivgi et al. (2023a, Lemma 3.4), replacing G, with G², which ensures that Lemma 4.1 still holds in our setting. Moreover, Lemma 4.4 remains valid. For Lemma 4.5, recall that f4, dF./(L (L + 1)2 given in equation (13). The noise from can be bounded as
2LFF = Σ
2Ldr (k 1)²
<
2Ld
S 4LdF?
(k +++13 1)2
k=0
k=
km0
18

---

A Paramcter-Frec and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
where the last inequality the fact that Σk= 1/k² =
Combining the modified lemmas and using equations (9) and (10), obtain that, with probability at least 1 6, the following upper bound on the optimality gap holds
(28t + F.) + 881 0 + 412d20s 4Ldr;
Ex=0 Fk/Fe
where we use the fact that fz-1 S Ft and $1-1 S
Applying the inequality va² + Sa+ b, the gap simplifies
(28: + Fe) F.). G (3, G + 20, Ld) + ALdr,
Σx Fk/F2
Finally, using the fact that G2 G2 and the triangle inequality 8r Ft + so, the gap becomes
01 + ( Ld)
20
ΣE Fk/Fi
C.3. Proof of Theorem 5.5
We begin by establishing the existence and uniqueness of the conditional expectation - According to Durrett (2019, Chapter 4. 1), suffices to verify that Fg C Fu and (x,,), - f(x.)l ) < co. By definition, we recall
that F8 = {A C 22 Q8} n Fo. which implies that F8 C Fo- To verify the integrability condition, we start from inequality (14), which states
2
ge
2
Σ Th (A, X x.) 2
Σ ne (V
(S (xx), X, - Xx),
k=
k=
for t I, T. Applying the upper bounds (Appendix B.2), we obtain
lgxl S Ld (Lemma 4.2), V (xx}]] Ld and | I 2Ld
[-
mk
gk
+2
Σ 7k A -x,
nhl M (xx) 3xx)]1[x= xxll Σ
1-1
$ dd
Σ
Th + 6Ld5
Tk
k=
k=
Since 7 = Cr/ with G¹ 2 d2, ,, it follows that
67
Given that Fn = r. S 38p < oo, it follows by induction that 8, < 0o and Ft < xo for all S T. Finally, by the Lipschitz continuity of f-), we obtain
If(x,) f(xx)) L| x,1 S L$r co.
Hence, Exf(x,,) - f(xx)l < co. Therefore, we conclude that the conditional expectation Exf(x+,) - f(xx) Fs] exists and is unique.
Now, we provide the proof of Theorem 5.5.
Proof of Theorem 5.5. Recall the definitions
Ôg w
Sq: Vt <
Σ nr P x
-x,)
x.) 5
Am
19

---

A Parameter-Fres Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Ω8 w W Vt S T, {
Σ 0=0
FA F - x+) < <bej.
with P(Ds)= 2 - and P(2s) 2 1 - 8. By Proposition 5.4, for any w E 928 n 925, have
f(x,) f(x.) s 20 f1. + su) G Ld)
S
Σx Fk/Fr
Combining this with equation (11), we obtain that for any E S2s n Sz. the following inequality holds
0 + 80) Ld)
TTT
f(x,,) - f(x.)= S co
log+
T
where is constant and Ty arg max En Fk/Ft. Since 0G,s Fr and G², are non-deceasing in & and S T, we derive
0g,o so) (w)( Vp-1 Ld)
Fr
f(Rm)) f(x.)= S co
log+
T
Moreover, from Proposition 5.3, we know that Fr S 38p for any w E Sig n lig. Substituting this yields
0r,550 CT- + Ld)
3380
f(x,,) - f(x.)= s 4cp
log
T
Recall that F& = : C G2g ) Fo is sigma field satisfying Fs C Fo and Eis nsts E Fz. Then, applying Lemma B.1, for any w E 12g n Ω2g, we have
07,480
E [
Gr-
Fx + Lad
330
[((()+)) - [(x+)
4ep
log
(24)
T
re
Using Lemma 4.2 and Lemma B.2, we can bound the conditional expectation of G follows
E[G Fi] = EEG =8 0r,6 log? (T' + 1)
Σ
EE gk 1311 + 1607,
K=0
08 log (T 1)(c2 16d
Since the square root function is concave, applying Jensen's inequality in Lemma B.3 gives
Bl G Jol S / E 820 0r, log, (T + 1) V cL2dT + 16 < 02, log, (T ()(VVVV + 4dE).
Substituting this back into equation (24), for any w E Ôg n we have
Vd. T.) a 8T, log,
[x)(),)) fxxx) S ci (L+ L)
80
(25)
/T
re
where is constant and oT, = 01,6 log, (T + 1). Moreover, we have
P( n 22)) 2 P((.s) + P()))) 12 1 28.
20

---

A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
C.4. Proof of Theorem 5.6
Proof. For a given T 2 2, let & E, where E\t is Bernoulli distribution defined by
1 P(E = 0) = T
1
and P(C = 1) = T
We first define the function f1 IR + R as
fi(x) L||x|11,
where -I 111 is the 4nonrm. The SZO for function f1 is constructed such that for any E IR and y E Rd the oracle returns evaluations Fi (x; E) and Fi (y: {) satisfying Fi (x:E) = L||x|| and (2(y: Llly || for all & drawn from E. This oracle clearly satisfies Assumption 2.7. Moreover, the function Fi (-: {) is convex and Lipschitz continuous with L1 = L for all &.
Next, we define another function f2 R Rs as
f2(x) L|[x -
where u = -1 11 Rd. The SZO for function f2 is constructed such that for any E Rd and y E IR4, it returns the evaluations F2(x; E) and Fz(y; E) satisfying
(x; 0) = [||x||1,
(x;;;) TL u/ (T - 1)L |x|11
F2(y;0) 0) = [1,
12 = T - u/|1 (T -1)//ll
Thus, we have FFa (2; 6)] = f2(z) for all z E (Rdd which satisfies Assumption 2.7. Moreover, we can verify that both F2(2; 0) and F2(z; 1) are convex and Lipschitz continuous on I, with the Lipschitz constant L2 = 2T
We initialize the algorithm x 1a. The probability of obtaining the identical information from both oracles F1 and F3 with 7 oracle calls is given by
(1-
T
1
for all T 2 2. This implies that any SZO algorithm cannot distinguish fi(-) and fe(-) in T SZO calls with probability at least 1/e. Therefore, near-optimal SZO algorithm A must achieve the nearly tight function value gaps for both functions with probability 1/e. In other words, algorithm A must output & satisfying
1.3 T.d L' TTd.
VoLi Xo - x1. and f2(8) f2 S 02
L ( T.))
Vdl2 - X2,0112
-()))
L's I.d.
VT
VT
where XI., arg min xeX" fi(x) = 0, X2,
A arg minxeR* f2(x) and 01, 02 g
R are two polylogarithmic
functions. Substituting L1 = L and L2 = 2TL, the corresponding bounds become
L i T T.d
d VT
L
||*||| S 0,
and
|| - u/l1 S 02
I T,d
1
Since (1 - 1/T) then the point & must satisfy
(
and | 2 d d
T 8
| < 0,
L's T.d
02
T,d
T L'
VT
Since the functions 0 and are poly-loga there exist sufficient large T such that
0 5 r.
- - 02
T.
d V
which leads to contradiction. Hence, we conclude that achieving an ideal parameter-fre stochastic reroth-order algorithm described in the theorem is impossible.
21


Reviews:
[{"review_id": "2RYCiE2eQ6", "reviewer": "Reviewer_ZPYR", "summary": "This paper addresses the stochastic optimization problem\n$$\n\\min_{x \\in \\mathcal{X}} \\mathbb{E}_{\\xi}[F(x, \\xi)],\n$$\nwhere each function $F(\\cdot, \\xi)$ is convex and $L$-Lipschitz, and\n$\\mathcal{X}$ is a simple convex set in $\\mathbb{R}^d$. The authors propose a\nparameter-free zeroth-order optimization method that achieves\n$\\epsilon$-accuracy (in terms of the objective function) with high probability\nin $\\tilde{O}(\\frac{d L^2 D^2}{\\epsilon^2})$ stochastic function evaluations&mdash;nearly\noptimal up to logarithmic factors.\n\nThe proposed method builds on DoG (Ivgi et al., 2023), a parameter-free\nstochastic gradient method with distance adaptation, applied to a randomized\nsmoothing of the objective.\n\nThe authors also present a version of their algorithm for unbounded domains,\nassuming a good estimate of $L$ is available. Additionally, they\nestablish a lower bound demonstrating that a fully parameter-free algorithm with\ncomplexity scaling as $\\tilde{O}(\\frac{d L^2 D_0^2}{\\epsilon^2})$ is impossible,\nimplying that any efficient parameter-free method must depend on the domain\ndiameter $D$, rather than just the initial distance $D_0$ to the solution.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1** The main novelty—adapting at each iteration rather than fixing it in advance—introduces only minor modifications to the DoG analysis. While this is a useful refinement, it does not introduce a fundamentally new idea.\n\n**A1** Thank you for your thoughtful review. We highlight our novelty as follows:\n\n1. Our method can achieve the near-optimal convergence with the smoothing parameter $\\mu_t=\\mathcal{O}(\\sqrt{d/t})$, which is larger than the counterparts in existing works such as $\\mu\\_t=\\mathcal{O}(\\sqrt{d/T})$(Shamir, 2017)  and $\\mu\\_{2t}=\\mathcal{O}(1/(d^2t^2))$ (Duchi et al., 2015). This is a new observation which improves the numerical stability.\n\n2. For the unbounded domain case, we establish the lower bound (Theorem 5.6) to show that achieving an ideal parameter-free stochastic zeroth-order algorithm is impossible, i.e., the algorithm cannot attain the near-optimal SZO complexity with only logarithmic dependence on problem parameters. Our lower bound construction considers the dependence on $d$ in the complexity (construct the $d$ dimensional function), which is more challenging than the lower bound for the first-order method that depends on the 1-dimensional function (Khaled & Jin, 2024).\n\n**Q2** The algorithm is truly parameter-free only when the domain is bounded and the complexity bound depends on the domain's diameter.\n\n**A2** Thank you for your suggestion. We will clarify the claim of \"parameter-free\" in revision.  For the unbounded problems, we provide the lower bound to show that it is impossible to achieve the near-optimal and parameter-free algorithm. Please see the second point in the last response.\n\n**Q3** There is a mistake in the formula $\\mu_t$ for Algorithm 1, which makes the final bound in Proposition 4.7 not scale-invariant. The correct formula is likely $\\mu\\_t=\\bar{r}\\_t\\sqrt{\\frac{d}{t+1}}$. \n\n**A4** Thank you for your careful review. You're right that the smoothing parameter should be $\\mu_t = \\bar{r}\\_t \\sqrt{\\frac{d}{t+1}}$.  The result of Lemma 4.5 should be modified to\n$$\n\\sum_{k=0}^{t-1}2L \\bar{r}\\_k \\mu\\_k\\leq 4L \\bar{r}\\_{t-1}^2\\sqrt{dt},\n$$\nwhere the exponent of $\\bar{r}\\_{t-1}$ changes from $1$ to $2$. Thus, Proposition 4.7 should be stated as:\n$$\nf(\\bar{x}\\_t)-f(x^*)\\leq\\frac{16\\theta\\_{t,\\delta}(\\bar{r}\\_t+s\\_0)\\big(\\sqrt{G\\_{t-1}}+Ld+L\\sqrt{dt}\\big)}{\\sum_{k=0}^{t-1} \\bar{r}\\_k/ \\bar{r}\\_t},\n$$\nwhich is scale-invariant.\nBased on above modification, the main result (Theorem 4.9) still holds.\nWe also update our implementation and empirical results are very similar to previous ones. Please see the link <https://anonymous.4open.science/api/repo/a-5532/file/response-ZPYR.pdf?v=abeb97c6>.\n\n**Q4** Assumption 2.6 is missing \"for all $ x,y\\in\\mathbb{R}^d$\".   \n\n**A4** Thank you for your careful review. We will involve the description for these variables in revision.\n\n**Q5** Line 163: The claim that \"this is more challenging\" is somewhat misleading.  In principle, $\\mu_t$ can be arbitrarily small, even zero, in which case finite differences reduce to a directional derivative. While choosing a very small may degrade numerical stability in practice, this is a separate issue unrelated to theoretical complexity bounds.\n\n**A5** Thank you for your valuable suggestion. In revision, we will clarify that the choice of $\\mu_t$ is important to the numerical stability, rather than the theoretical complexity bounds. \n\n**Q6** Lemma A.4: The reference to Shamir (2017, Lemma 9) seems incorrect.\n\n**A6** Thank you for your careful review. The result of Lemma A.4 appears at the beginning of the proof of Shamir (2017, Lemma 9), which can be found at the bottom of page 6 (not the final result of Lemma 9). We will clarify this point in revision.\n\n**Q7** Typos: \"differed\" (line 169),  \"soothing\" (line 267).\n\n**A7** We appreciate your careful review. We will correct the typos in revision.\n\n**Q8** The paper assumes that the original objective is Lipschitz. What if it is Lipschitz-smooth? Can the proposed method still be applied, and what would its convergence rate be?\n\n**A8** Thank you for your insightful question. \n\nFor the bounded setting, our proposed method remains applicable. We assume that $F(\\cdot;\\xi)$ is $M$-smooth, i.e., $\\Vert \\nabla F(x)-\\nabla F(y)\\Vert \\leq M\\Vert x-y\\Vert$ for all $x,y \\in \\mathcal{X}$.\nLet $x^*\\in \\mathcal{X}$ be the solution.\nIt follows that $\\Vert \\nabla F(x)\\Vert\\leq\\Vert\\nabla F(x^*)\\Vert+\\Vert\\nabla F(x)-\\nabla F(x^*)\\Vert\\leq\\Vert\\nabla F(x^*)\\Vert+M\\Vert x-x^*\\Vert\\leq\\Vert\\nabla F(x^*)\\Vert+MD_\\mathcal{X}$ for all $x\\in \\mathcal{X}$.\nThus, the function $F(\\cdot;\\xi)$ is $(\\Vert\\nabla F(x^*)\\Vert+M D_\\mathcal{X})$-Lipchitz on the domain $\\mathcal{X}$.\nHence, we can directly apply Theorem 4.9 to achieve the convergence rate.\n\nFor the unbounded setting, the additional assumption such as bounded variance for the stochastic gradient (Ghadimi & Lan, 2013) is typically required. \nIt seems that our analysis cannot be directly applied to this case.", "claims_and_evidence": "The claims made in the paper are well-supported, with each theorem and lemma\naccompanied by a corresponding proof.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem at\nhand.", "theoretical_claims": "I reviewed the main theoretical claims and assessed the general proof techniques\nbut did not verify all details rigorously.", "experimental_designs_or_analyses": "I examined the experiments and found no major issues.", "relation_to_broader_scientific_literature": "This paper integrates two established optimization techniques:\n\n1. *Randomized smoothing*, which approximates the original objective via a\n   smooth surrogate, enabling efficient stochastic gradient estimation (Duchi et\n   al., 2012; Yousefian et al., 2012; Shamir, 2017; Nesterov & Spokoiny, 2017;\n   Gasnikov et al., 2022; Lin et al., 2022). The specific smoothing method used\n   here&mdash;uniform smoothing over the Euclidean ball&mdash;has been\n   extensively studied in (Duchi et al., 2012; Shamir, 2017; Gasnikov et al.,\n   2022).\n\n2. The *DoG algorithm* (Ivgi et al., 2023), which enables efficient\n   parameter-free stochastic optimization of convex functions.\n\nMuch of the analysis in this paper builds on the proofs in (Ivgi et al., 2023),\nleveraging known properties of randomized smoothing from (Shamir, 2017).", "essential_references_not_discussed": "I have not identified any essential references missing from the discussion.", "other_strengths_and_weaknesses": "**Strengths:**\n\n1. This is the first (to my knowledge) parameter-free algorithm for zeroth-order\n   stochastic optimization. The presentation is concise and generally clear.\n\n1. The lower bound in Theorem 5.6 is a valuable theoretical contribution (though\n   I have not fully verified its correctness).\n\n**Weaknesses:**\n\n1. The paper primarily combines existing results from (Ivgi et al., 2023) and\n   (Shamir, 2017). The proposed algorithm is essentially DoG applied to a\n   smoothed objective with a carefully chosen smoothing parameter $\\mu$. The\n   complexity bound follows directly from prior DoG results (Ivgi et al., 2023)\n   and  established bounds on the second moment of stochastic gradients for\n   the smooth approximation (Shamir, 2017). The main novelty&mdash;adapting\n   $\\mu_t$ at each iteration rather than fixing it in advance&mdash;introduces\n   only minor modifications to the DoG analysis. While this is a useful\n   refinement, it does not introduce a fundamentally new idea.", "other_comments_or_suggestions": "1. The claims that the method is \"parameter-free\" in the Abstract and early\n   sections of the paper require clarification. The algorithm is truly\n   parameter-free only when the domain is bounded and the complexity bound\n   depends on the domain's diameter. For unbounded problems (or when results\n   depend on the initial distance $D_0$ rather than $D$), the method requires an\n   upper bound on the stochastic gradient norm.\n\n1. There is a mistake in the formula for $\\mu_t$ in Algorithm 1, which makes the\n   final bound in Proposition 4.7 not scale-invariant. The correct formula is\n   likely $\\mu_t = \\bar{r}_t \\sqrt{\\frac{d}{t + 1}}$.\n\n1. Assumption 2.6 is missing \"for all $x, y \\in \\mathbb{R}^d$\".\n\n1. Line 163: The claim that \"this is more challenging\" is somewhat misleading.\n   In principle, $\\mu_t$ can be arbitrarily small, even zero, in which case\n   finite differences reduce to a directional derivative. While choosing a very\n   small $\\mu_t$ may degrade numerical stability in practice, this is a separate\n   issue unrelated to the theoretical complexity bounds.\n\n1. Lemma A.4: The reference to Shamir (2017, Lemma 9) seems incorrect.\n\n1. Typos: \"differed\" (line 169), \"soothing\" (line 267).", "questions_for_authors": "1. The paper assumes that the original objective is Lipschitz. What if it is\n   Lipschitz-smooth? Can the proposed method still be applied, and what would\n   its convergence rate be?", "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": "hFM18cCMcO", "reviewer": "Reviewer_7JXP", "summary": "This paper proposes a parameter-free stochastic zeroth-order method that achieves near-optimal rate in the convex setting with a bounded domain. The authors also consider the unbounded domain case and prove that it is impossible to construct an ideal parameter-free algorithm in this setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and appreciation of our work.\n\n**Q1** Figure 3 has not been mentioned in the main text. Add a description to it.\n\n**A1** We sincerely thank you for your careful review. \nWe will modify the text in lines 436-438 of the left column to include a clear reference to Figure 3.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I do not have the time to check all the proofs. To what I have verified, everything looks fine.", "experimental_designs_or_analyses": "The experimental design is reasonable.", "relation_to_broader_scientific_literature": "This paper considers parameter-free stochastic optimization, several related works are published in past ICML events.", "essential_references_not_discussed": "The literature is sufficiently covered.", "other_strengths_and_weaknesses": "Strengths:\n- Clear writing with a nice flow of ideas.\n- The first parameter-free stochastic zeroth-order method in the convex setting, which is a solid contribution\n- The impossibility result is interesting which reveals the fundamental necessity of a bounded domain.\n- The robustness of the parameter setting of POEM is numerically verified\n\nWeaknesses:\nNA", "other_comments_or_suggestions": "Figure 3 has not been mentioned in the main text. Add a description to it.", "questions_for_authors": "NA", "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": "2C6tufnDsK", "reviewer": "Reviewer_dAwi", "summary": "This paper introduces a novel parameter-free zeroth-order optimization algorithm named POED for stochastic convex optimization problems. The key idea is to eliminate the need for parameter tuning including learning rate and smoothing parameter. Inspired by difference of gradients (DoG), the proposed method leverages a difference of finite difference strategy to set the learning rate and use an adaptive smoothing parameter. The authors prove that POED achieves near-optimal SZO complexity under bounded domain assumption while impossible to achieve parameter-free algorithm in unbounded setting. Finally, numerical experiments on several datasets demonstrate the superiority of POEM.\n\n## update after rebuttal\n\nMost of my concerns have been addressed during the rebuttal.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1** The empirical evaluation is limited to a few datasets and could be extended to cover more diverse and large-scale scenarios.\n\n**A1**  Thank you for your suggestion.\nWe have addressed your comment by including the experiments on the higher-dimensional datasets \"qsar\" ($d=1,024$, $n=1,687$) from UCI machine learning repository and \"gisette\" ($d=6,000$, $n=5,000$) from LIBSVM repository. \nPlease see link <https://anonymous.4open.science/api/repo/a-5532/file/response-dAwi.pdf?v=78140e95> for the experimental results.\nWe can observe that our POEM also performs better than baselines.\n\n**Q2** Can you elaborate on the challenges and potential modifications required to extend POEM to nonconvex optimization problems?\n\n**A2**  Thank you for your question.\nIt is still unclear how to extend POEM to nonconvex optimization problem.\nThe convexity plays a crucial role in our theoretical analysis:\n\n1. In Equation (8), we bound the function value gap by using Jensen’s inequality, which relies on the convexity of $f(\\cdot)$.\n\n2. In Equation (9) and the poof of Lemma C.3, we use the first-order condition in Lemma A.1 which requires the convexity of the smooth surrogate $f_\\mu(\\cdot)$, and the convexity of $f_\\mu(\\cdot)$ comes from the convexity of the objective $f$ (see Lemma 2.8).\n\nFor the nonconvex problem, it is possible to introduce the online-to-nonconvex conversion [1-3] into our framework to attain the nearly-tight upper bound. However, it seems not to be a direct extension. We believe this is a good future direction. \n\nReferences\n\n[1] Ashok Cutkosky, Harsh Mehta, Francesco Orabona. Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. ICML 2023.\n\n[2] Guy Kornowski, Ohad Shamir. An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization. JMLR 2024.\n\n[3] Kwangjun Ahn, Gagik Magakyan, Ashok Cutkosky. General framework for online-to-nonconvex conversion: schedule-free SGD is also effective for nonconvex optimization. arXiv:2411.07061, 2024\n\n**Q3** What is the computational cost associated with computing the adaptive step size? The computation of the adaptive step size seems need a copy of initial parameters weight. How does this overhead compare with that of standard zeroth-order methods in large-scale applications and do you think there exists a memory-efficient way for the implementation?\n\n**A3** Thanks for your insightful question.\nEach iteration of POEM requires the computational cost of ${\\mathcal O}(d)$ to access $||x_t-x_0||$ and $||g_t||$ to determine the step size. \n\nCompared with standard zeroth-order methods, POEM needs to additionally maintain the initial point $x_0$, which requires storing additional $d$ floating point numbers in general.\nHowever, the domains of many real applications contain the origin.\nIn such case, we can simply set $x_0=0$  to avoid the additional memory cost to store $x_0$. \n\n**Q4** Recent research has focused on fine-tuning large language models with zeroth-order optimization algorithms while sensitive to the selection of learning rate ([1], [2]). The proposed method seems to be a promising way for solving this problem. Do you think POEM is suitable for large-scale applications like training/fine-tuning large-scale models?\n\n**A4** Thanks for your constructive suggestions.\nThis work focuses on convex optimization, while training/fine-tuning large-scale models typically corresponds to nonconvex optimization.\nAs we mentioned in A2, our theory cannot be directly extended to the nonconvex case.\nFollowing your suggestion, we are currently attempting to adapt POEM to the fine-tuning of large-scale models. We have not yet determined whether POEM is suitable for this task.", "claims_and_evidence": "The paper claims that (a) POEM is a parameter‐free method, (b) it achieves near‐optimal SZO complexity under convexity, Lipschitz conditions and bounded domain assumptions. To support thest claims, the authors provide rigious theoretical analysis that establish high-probability convergence guarantees. The experimental results also verify the superiority of POEM. Overall, the claims are well supported by both analysis and experiments.", "methods_and_evaluation_criteria": "POEM is designed to automatically adjust its step size and its smoothing parameter. This design avoids the typical need to manually set these hyperparameters, which is well aligned with problem of parameter-free optimization problems. \nThe analysis centers on standard metrics in zeroth-order optimization, such as the function value gap and the SZO complexity. These criteria are consistent with the established literature.", "theoretical_claims": "The mian theoretical claims include the convergence rate guarantees for bounded and unbounded domains. The proofs build on well-established lemmas and techniques. I didn't carefully check all the proofs but the theoretical results seem to be sound.", "experimental_designs_or_analyses": "The experimental design is straightforward and relevant. The use of standard benchmarks helps validate the algorithm’s practical performance. However, the scope of the experiments is somewhat limited in terms of dataset diversity and scale, as well as the scale of the model scale. More extensive empirical validation could further bolster the claims.", "relation_to_broader_scientific_literature": "The work is well situated within the current literature and clearly identifies the gap it fills—namely, the lack of parameter-free methods in zeroth-order optimization that achieve near-optimal complexity.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strenths:\n\n1) To the best of my knowledge, this is the first work to explore a parameter-free zeroth-order optimization.\n\n2)  Comprehensive theoretical analysis with convergence guarantees matching lower bounds.\n\nWeaknesses:\n\n1) The empirical evaluation is limited to a few datasets and could be extended to cover more diverse and large-scale scenarios.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "1. Can you elaborate on the challenges and potential modifications required to extend POEM to nonconvex optimization problems?\n\n2. What is the computational cost associated with computing the adaptive step size? The computation of the adaptive step size seems need a copy of initial parameters weight. How does this overhead compare with that of standard zeroth-order methods in large-scale applications and do you think there exists a memory-efficient way for the implementation?\n\n3. Recent research has focused on fine-tuning large language models with zeroth-order optimization algorithms while sensitive to the selection of learning rate ([1], [2]). The proposed method seems to be a promising way for solving this problem. Do you think POEM is suitable for large-scale applications like training/fine-tuning large-scale models?\n\n[1] Fine-Tuning Language Models with Just Forward Passes.\n\n[2] Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuning.", "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": "NkpZosAztk", "reviewer": "Reviewer_7pJ3", "summary": "The paper gives a parameter-free zeroth-order algorithm for convex and Lipschitz continuous stochastic functions $f(x) = E[F(x,\\xi)]$ over a convex and compact (section 3/4) or convex and closed (section 5) set. It achieves optimal convergence rates (up to a logarithmic factor) without knowledge of the Lipschitz parameter or the diameter of the constraint set $X$. The parameter-free convergence rates are achieved using an AdaGrad style tuning and the current maximum norm distance to the initial iterate $x_0$. The theoretical findings are supported by illustrating experiments.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We highlight our technical contribution and new insights as follows:\n\n1. To the best of our knowledge, the proposed POEM is the first parameter-free algorithm for zeroth-order stochastic optimization, which is also mentioned by all other reviewers.\n\n2. Our method can achieve the near-optimal convergence with the smoothing parameter $\\mu_t={\\mathcal O}(\\sqrt{d/t})$, which is larger than the counterparts in existing works such as $\\mu_t={\\mathcal O}(\\sqrt{d/T})$ (Duchi et al., 2015)  and $\\mu_{2t}={\\mathcal O}(1/(d^2t^2))$ (Shamir, 2017).\nThis is a new observation which improves the numerical stability in the step of finite difference.\n\n3. For the unbounded domain case, we establish the lower bound (Theorem 5.6) to show that achieving an ideal parameter-free stochastic zeroth-order algorithm is impossible, i.e., the algorithm cannot attain the near-optimal SZO complexity with only logarithmic dependence on problem parameters.\nOur lower bound construction considers the dependence on $d$ in the complexity (construct the $d$ dimensional function), which is more challenging than the lower bound for the first-order method that depends on the 1-dimensional function (Khaled \\& Jin, 2024).", "claims_and_evidence": "Claims are clear and supported.", "methods_and_evaluation_criteria": "Primarily theoretical work, hence, benchmark datasets are not relevant.", "theoretical_claims": "To the best of my understanding, theoretical claims are correct.", "experimental_designs_or_analyses": "The paper contains a small experimental part with numerical experiments illustrating the theoretical findings. To the best of my understanding, the experimental design is sound and valid.", "relation_to_broader_scientific_literature": "The contributions of this paper are rather incremental. (for more details, see weaknesses)", "essential_references_not_discussed": "To the best of my knowledge, all relevant literature is discussed.", "other_strengths_and_weaknesses": "Strengths: \n- This work is very clearly written. \n\nWeaknesses:\n- To the best of my understanding, the results and techniques are rather incremental. Most results follow directly with small modifications (extensions from first- to zeroth-order) of the work by Ivgi et al '23a combined with the zeroth order gradient estimation in Shamir '17. Specifically, the similarities in techniques to the work by Ivgi et al are -to the best of my understanding- very strong.", "other_comments_or_suggestions": "While the paper is very clear and well-written, I think the contribution is rather incremental. Many of the theoretical results share similarities with the results in Ivgi et al and Shamir, up to the point that the proofs follow very similar ideas and structures. \n\nI think the paper would profit a lot from clarifying what its technical contribution and new insights are. \n\nI am happy to revise my evaluation if the authors can convince me that there is a significant difference between existing work and their contribution.", "questions_for_authors": "See weaknesses and comments.", "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": {"ethical_review_concerns": "none."}}]

Author rebuttal:

Meta-review: This paper proposes a parameter-free zeroth-order algorithm for stochastic optimization. It is an extension of some recent parameter-free first-order algorithms. It addresses the important issue that under certain scenarios first-order oracle is not available but only zeroth-order oracle is available. This is a nice contribution to the literature of parameter-free algorithms for stochastic optimization.
Decision: Accept (poster)