General Stability Analysis for Zeroth-Order Optimization Algorithms
Authors: Xinyue Liu
Hualin Zhang
Bin Gu
Hong Chen
Venue: ICLR 2024 poster (2024)
Keywords: Stability Analysis; Zeroth-Order Optimization; Black-Box Learning
Primary area: learning theory

Abstract: Zeroth-order optimization algorithms are widely used for black-box optimization problems, such as those in machine learning and prompt engineering, where the gradients are approximated using function evaluations. Recently, a generalization result was provided for zeroth-order stochastic gradient descent (SGD) algorithms through stability analysis. However, this result was limited to the vanilla 2-point zeroth-order estimate of Gaussian distribution used in SGD algorithms. To address these limitations, we propose a general proof framework for stability analysis that applies to convex, strongly convex, and non-convex conditions, and yields results for popular zeroth-order optimization algorithms, including SGD, GD, and SVRG, as well as various zeroth-order estimates, such as 1-point and 2-point with different distributions and coordinate estimates. Our general analysis shows that coordinate estimation can lead to tighter generalization bounds for SGD, GD, and SVRG versions of zeroth-order optimization algorithms, due to the smaller expansion brought by coordinate estimates to stability analysis.

Published as a conference paper at ICLR 2024
GENERAL STABILITY ANALYSIS FOR ZEROTH-ORDER OPTIMIZATION ALGORIHTMM
Xinyue Liu 1 Hualin Zhang 4, Bin Gu Hong Chen 1.2- !College of Informatics, Huazhong Agricultural University, China FEngineeiing Research Center of Intelligent Technology for Agriculture, China Schooo of Artificial Intelligence, Jilin University, China
'Mohamed bin Zayed University of Artificial Intelligence, UAE 3xy366 hzau, edu. ch,zhanghual 199 gma 1 com, lsquuiinegrn i1. com, chenh@maile hzau. www..edu.uc.. on
ABSTRACT
Zeroth-order optimization algorithms are widely used for black-box optimization problems, such as those in machine learning and prompt engineering, where the gradients are approximated using function evaluations. Recently, a generalization result was provided for zeroth-order stochastic gradient descent (SGD) algorithms through stability analysis. However, this result was limited to the vanilla 2-point zeroth-order estimate of Gaussian distribution used in SGD algorithms. To address these limitations, we propose a general proof framework for stability analysis that applies to convex, strongly convex, and non-convex conditions, and yields results for popular zeroth-order optimization algorithmss, including SGD, GD, and SVRG, well as various zeroth-order estimates, such 1-point and 2-point with different distributions and coordinate estimates. Our general analysis shows that coordinate estimation can lead to tighter generalization bounds for SGD, GD, and SVRG versions of zeroth-order optimization algorithms, due to the smaller expansion brought by coordinate estimates stability analysis.
INTRODUCTION
Zeroth-order (ZO) optimization algorithms have gained widespread use in solving black-box opti- mization problems, particularly in machine learning fields (Chen et al. [2017] Kurakin et al.] [0066] Madry et al., 2017] (Sun al., (022). In such problems, obtaining the explicit gradient is often either unattainable or too expensive, and only the function value of the output can be obtained. For instance, pre-trained language models (PTMs) like GPT-3 (Brown et al. 2020) allow only user-designed task- specific prompts to query them, and their gradients usually unavailable. Similarly, in scenarios where the internal structure and training data deep neural network (DNN) are unknown, as in (Papernot et al., 2017), and only the input and output are accessible, the black-box attack can be launched to manipulate the model output and cause incorrect predictions. Here, 70 algorithms can achieve excellent performance, comparable known (Sun et al. 2022 Papernot et al.) (017).
better than white-box models where gradients
In ZO optimization algorithms, the approximation of gradients is achieved by using function values. The accuracy of these zeroth-order (ZO) gradient estimates is critical for determining the convergence rate and optimal learning rate settings. Therefore, conducting research to improve the accuracy of ZO gradient estimates is of utmost importance. There are three main categories of ZO gradient estimates: I 1-point (Flaxman et al. 2004), 2-point (Nesterov Spokoiny 2017 Duchi et al. 2015) with different distributions, and coordinate estimates. As the number of function evaluations increases, the accuracy of the gradient estimates improves (Duchi et al. 2015). When the number of function evaluations reaches the problem dimension d, it is preferable to use the deterministic coordinate-wis. gradient
"Corresponding authors.

---

Published as a conference paper at ICLR 2024
estimate instead of the 1 1-point and 2-point gradient estimates with random directions. This estimate has a significantly lower approximation error (Kiefer & Wolfowitz 1952. Berahas et al. 2022 Lian
et al. 2016), of order O (du²) (where μ is the smoothing parameter).
Multiple ZO algorithms have been proposed to address the core problem of minimizing the loss function in optimization. Initially, the ZO gradient descent (ZO-GD) algorithm (Nesterov & Spokoiny 2017) was the focus of the ZO optimization algorithm field. Yurii et al. (Nesterov & Spokoiny 2017) proposed the ZO-GD algorithm that employs 2-point Gaussian random gradient estimator and established convergence guarantees for it. Subsequently, Saeed et al. (Ghadimi & Lan 2013)
introduced the ZO-SGD algorithm that uses the same estimator. However, due to the high variance of
the ZO stochastic gradients, the convergence rate of ZO-SGD is limited to O (V/TT) (Ghadimi
Lan 2013) for non-convex problems, where is the total number of iterations. To accelerate its convergence, some variance reduction strategies commonly used in first-order optimization algorithms, such as SVRG and SAGA, were introduced into the ZO setting. These strategies have been shown be effective in the first-order setting and are also effective in the ZO setting. The ZO-SVRG (Liu et al. 2018 8 Ji et al. (019)) and ZO-SAGA (Huang et al. 2019) algorithms can improve the convergence rate O (1/T).
As mentioned above, research on ZO algorithms in the optimization field is extensive and com- prehensive. However, there is only one generalization study that focuses specifically on ZO-SGD (Nikolakakis et al., 2022). In their study, Konstantinos E. et al. (Nikolakakis et al.) (0022) provide generalization results of ZO-SGD under a two-point Gaussian smoothing estimate and demonstrate that the algorithm has comparable generalization performance to SGD in non-convex environments when using diminutive step sizes. While Konstantinos E. et al. (Nikolakakis et al. 2022) presents surprising results, it does not encompass the diverse range of estimates and optimization algorithms in the ZO optimization field. In contrast to the limited research on ZO generalization, first-order analysis has yielded more diverse body of work, specifically regarding algorithms such as SGD (Hardt eet af. 2016), GD (Hoffer et al., 2017]] Charles & Papailiopoulos 2018). and stage-wise learning strategy (Yuan et al., 2019). These discussions have inspired us further explore the generalization performance of ZO algorithms.
To address the limitations of existing research, this paper focuses on studying the generalization behavior of a more comprehensive ZO optimization algorithm and provides a more inclusive proof framework. The contributions of this work are as follows:
We propose a more general proof framework for ZO optimization algorithms. Leveraging our proof framework, we provide for the first time generalization bounds for different 70 algorithms, including ZO-SGD, ZO-GD, and ZO-SVRG with different 70 gradient estimates under convexity and non-convexity conditions. To the best of our knowledge, this is the first work on generalization analysis for ZO-SVRG.
ZO optimization algorithms differ from first-order optimization algorithms in that they approximate gradient values using function values. As a result, approximation errors introduce new expansions for generalization analysis. Our results show that, ZO algorithms that use coordinate estimates lead to tighter generalization bounds for ZO-SGD, ZO-GD and ZO-SVRG, and importantly same to the ones of first-order algorithms.
PRELIMINARIES
2.1 NOTATIONS
Throughout this paper, we N (0, I) denote the standard normal distribution on R.d. We denote the ball in Rd with radius centered at by (v, and gd-1(e.r) denotes the fa-sphere in Rd with radius r centered at v. We also use the abbreviations Bd = [0, 1), S = gd 1 (0, 1), and 1 for the all-ones vector.
2.2 PROBLEM SETUP
Let D = { be the training dataset of size n, where each sample is independently identically distributed over an unknown distribution D. For prescribed model w, its performance on single
2

---

Published as a conference paper at ICLR 2024
Table 1: A list of the generalization algorithms. (NC, C and SC are the abbreviations of nonconvex, convex, and strongly convex, respectively. T is the whole iteration number, the sample size, C' is constant, beta is the smoothness constant, and S denotes the stage number of ZO-SVRG. The corresponding details for SVRG are provided in the appendix.
bounds developed here in for zeroth-order optimization
Algorithms
Reference
Gradient Estimator
Problem
Generalization Bound
aC TCTII /n
NC
SGD
Hardt et al.
2016
None
C
(log T/n)
SC
O (1/n)
Nikolakakis et al. (2022)
2-point
NC, C, SC
O(T/n)
Ours
2-point
NC, C, SC
(T/n)
Ours
1-point
NC, C, SC
T/n TFLOVA
ZO-SGD
T aC /n
NC
Ours
Coordinate-wise
C
O (log T/m) O (1/n)
SC
NC
O (T /n)
GD
Nikolakakis et al. (0222)
None
C
O (log T T/m)
SC
(1/nn)
Nikolakakis al. (2022)
2-point
NC
O
Ours
1-point
NC, C, SC
O (TC (T
NC
Ours
Coordinate-wee -wie
C
(log
ZO-GD
SC
(1/n)
NC
SVRG
Ours
None
C
O S25C
SC
O (S/n)
1-point 2-point
NC, C, SC
O S00
NC, C, SC
S3BC
NC
S33C
ZO-SVRG
Ours
Coordinate-wise
C
S25C (n)
SC
(S/m)
example z is measured by the loss function [wr, 2). this paper, we are particularly interested in the generalization performance of model w on D measured by the following expected risk:
R(w) = Ef-lff 2)].
Since is unknown, optimizing R(w) directly is not possible. In practice, we measure the model w by the empirical risk based the training dataset D:
1 Σ f(w, 21) n
RD(w)=
For (randomized) algorithm A trained on dataset D with output A(D)) the generalization error is defined as the gap between the population risk and empirical risk:
Egen = ED.A (D.A(B(A(D)) (A()))
A useful tool for analyzing the generalization error is the stability, which measures the sensitivity of the algorithm's output w.r.t. the perturbation of a training dataset. The formal definition of uniform stability is as follows:
Definition 1 (Uniform Stability). A (randomized) algoritim A has uniform stability if for all D, D' Z that differ in one sample, have sup, (Al((A(D)))) ((A(D')

---

Published as a conference paper at ICLR 2024
An important relationship between the uniform stability and generalization error bound is implied by the following lemma:
Lemma (Hardt et al. 2016), Theorem 2.2). Let A be uniform stable, then |Egenl S e.
The goal of this paper is to derive uniform stability bounds for class of zeroth-order (randomized)
algorithms with update rule of the form:
W+++1 wt (u:)(
4
where (y(wr) depends only on the evaluations the function values. Denote by fw,, 2) the gradient estimation of the true gradient Vf(w,, 2), which will be detailed described in the next subsection. Then, the update rule Eq.equation covers a wide range of gradient estimation based zeroth-order (gradient-free) free)) algorithms. For example, zeroth-order gradient descent (ZO-GD) with Gy(we, =) (RD(w:): zeroth-order stochastic gradient descent (ZO-SGD) with gy(we, 2) Vf(w; ),), where 2,, E D is a randomly sampled example at itcration t; zeroth-order stochastic variance reduced gradient (ZO-SVRG) with Gy(w,) = V f(w,, ) V fw, =i,) + V (w), where the final output of ZO-SVRG in the last stage. Now formally describe the gradient estimations that are commonly used in the literature of zeroth-order optimization.
2.3 ZO GRADIENT ESTIMATION
Random Gradient Estimation. Intuition for zeroth-order gradient estimator follows by the fact about definition of directional derivative that:
(w, u)u] = EK f((w), u u] = f when
E juu |
I,
where f'(w, u) == lim fl++pa) denotes the directional directive of function ff with respect to direction vector u at point w.
Lemma 2 (Baydin et al. (202)), Lemma & 2). Let u [u'..... IT and u', 1.... are i.i.d random variables sanisfying E Eju') O. Var[u"] 1, then we have E(uu" 1 I.
Note that, several random distributions satisfy the above condition. For example, the standard multi- variate normal distribution: N (0, I), uniform distribution over ball or a sphere: Unif( + 2Bdd)
and Unif( Vds dddd Based on the fact that E [(w+we)-f(eer u f(w+ww) u, the averaged 1-point
"
gradient estimate of f has the following generic form:
(((w)=
Σ
f(w + puu))R
μ.
where ux, A = 1,..., K are i.i.d random vectors satisfying Lemma 2 It is easy to verify that the 1-point gradient estimate suffers from large variance. As comparison, the averaged 2-point gradient estimate can significantly reduce the variance:
(w+tue)) f(w) uks
forward difference, central difference.
(w) = K E
(6)
2p
Deterministic Coordinate- Wise Gradient Estimation: When the number of function evaluations reaches the problem dimension d, then instead of using randomized (trections(u:). one can employ the deterministic coordinate- wise gradient estimate:
f(w+ [(w) e;
forward difference,
f(w) =
flw+t pe:) ftw--(www- pea) e,
central difference.
2
where e; d denotes the i th elementary basis vector, with I the i-th coordinate and O elsewhere
4

---

Published as a conference paper at ICLR 2024
3 A GENERIC GENERALIZATION ANALYSIS FRAMEWORK OF ZO OPTIMIZATION
In this section, we will establish a generic generalization analysis framework for zeroth-order optimization with update rule of the form Eq.equation 4 By derivation, we conclude that as the approximate gradient approximates the true gradient, the generalization boundary will also tighten with this approximation. The smaller the error of between the approximate gradient and the true gradient is, the better the generalization of the model is.
Let G+(+) and ()) be update rules of first-order methods under samples D and D' respectively, which take the form of
Ge(wr)= wt arg(ur, zi.), G(((e)) w wi arg(ur, 2/,),
(8)
where G(w,, = and ((w,, z4,) represent the gradient estimation of V (l)(w)) and V (w)) via first-order oracle. Similarly, let Gc(-) and (.) () be the update rules of zeroth-order methods in Eq.equation i.e.
Ge(wr)= w -
(wr, z,), -
(w())) = wi a (w,))4,),
(9)
where gy 2.,) and Gy(we; =1,) denote the gradient estimation via zeroth-order oracle. Hardt et al. (2016) provided a proof framework for SGD, but this framework does not apply more complex algorithms. Therefore, we present two new sequences of update rules.
Definition (Hardt et al.) (216)), Definition 2.3). An update rule is o-bounded if supwen || (w) - w| I and is -expanssive if sup supp wen ||G - (w)) S n ||w 1oo--0 w/l.
With these two properties, we can establish the following lemma to demonstrate how the update sequence of the model diverges when the training set is perturbed.
Lemma 3 (Growth Recursion). Let {G and (G be two update sequences. Let wo w/ be the starting point, W -G(ew)) and w/+1 G (w,)) Then for any We, w/ E IR. and t 2 0, we have
G (wi) - G² (w]) s { (1 + w/)luwr - will + 04o [|w, - will + 20,0,,2 + 0,0
(G,() C,0,, ( + ()())
E
The generalization analysis of zeroth-order optimization is similar to the proof framework pro- posed in Hardt et al. (2016). Here, 1) is the expansive factor generated by the first-order algorithms based on different convexity properties. vy is induced by the approximation error of the zeroth- order gradient estimation. And different estimation would induce different n/-- Particularly, in the case of coordinate-wise estimation, there won't 't introduce a new 1/. Thus the shrinkage ef- feet brought about by 1) becomes evident under convex and strongly convex conditions. Tz, is induced by the approximation error of the zeroth-order gradient estimation, which is an upper bound of E [[ 2;,)
(We, 2s,) - (G(w', 2,, - Gy 22,)) []. 02.2 is induced by the fact that the first-order update rule G.(-) is ot,2 -buunded at iteration t. Finally, or,3 is induced by another approximation error of the zeroth-order gradient estimation, which is an upper bound of (g =1,) - Gy Gy(w,, I1
E [l 2
Gy(wr, =.,) -
Lemma 4. Consider zeroth-order algorithms with final output wT and wh with respect to dataset D. D', respectively. Denote 8x == ||r w/, || and vtg E {0, 1, n1). define the event Essn ==
f5., = 0}, we have
T
El
<
Σ t=t++1
(1 1 n m))²
T-t a, [[1- JJ), +n 12 + 023)]
Finally, we can obtain the generalization error through the following lemma:
Lemma (Hardt et al. 20166) Lemma 1). Assume that the loss function f(,,2) is L-Lipschitz for all z. Let D and D' be two samples of size that differ in only one sample. Denote by wT and w/ the final output of zeroth-order algorithms with respect to dataset D and D' respectively. Then for every and to E {0, ,,,,.,,),,, n), have E, f(r,, 2) f( =)] L.( + to sup,., f(w, 2)/n.
5

---

Published as a conference paper at ICLR 2024
4 APPLICATIONS
In this section, we apply the generic generalization analysis to different zeroth-order algorithms such as zeroth-order stochastic gradient descent, and zeroth-order stochastic variance reduced gradient.
4.1 ZO-SGD GENERALIZATION ANALYSIS
ZO-SGD with 1-Point Gradient Estimation. To begin with, we first define some basic notations used in zeroth-order stochastic gradient descent with averaged 1-point gradient estimation of the form Eq.equation 5 At the f-th iteration, we uniformly randomly select sample index i, from [m]. and then update parameter wy by
WG++1 = Wi are V. [Wi, zic),
(10)
where {ar} is sequence of positive step-size and V f(wr, 24,) denotes the 1-point gradient estimation of form equation Under the Lipschitz continuous and smooth condition, ZO-SGD with 1 1-point gradient estimation has the following generalization bound.
Theorem (Nonconvex), Assume that the loss f(,,2) E [0. 1] is L-Lipschitz and 3-smooth for all Z. Consider the update rule Eq.equation [0 with T the total number of iterates, on C/t for some (fixed) C > O and for all t I T. Then the generalization error of 20-SGD with 1-point gradient estimation bounded by
Te/+1/e
Egen S +
CCL/)
T LLCV
n
ZO-SGD with 2-Point Gradient Estimation. Then we consider the generalization error bound of ZO-SGD with 2-point gradient estimation. As formulated in Eq.equation 6 there are two general forms of 2-point gradient estimation: central difference and forward difference. At the t-th iteration, we uniformly randomly select sample index i, from [n]. and then update parameter we by:
Wi+1 = wi ar V (wi, =w))
(11)
where {ar} is sequence of positive step-size and VK f'W,, =i,) denotes the 2-point gradient estimator of form equation [6] Under the same conditions as ZO-SGD with 1 1-point gradient estimation, found that both the forward difference version and central difference version update rule would derive the same expansive factor and tighter generalization error bound the same order.
Theorem 2 (Nonconvex), Assume that the loss f(., 2) [0. 1] is L-Lipschitz and 3-smooth for all E Z. Consider the update rule Eq.equation 77 with T the total number of iterates, < C/t for some (fixed) C > O and for all t < T. Then the generalization error of ZO-SGD with 2-poins gradient estimation is bounded by Egen $ (1 (BC)-1)² (1 e)CT) 3Te/2n.
ZO-SGD with Coordinate- Wise Gradient Estimation. Then we consider the generalization еπиоr bound of ZO-SGD with coordinate- -addiiitte--ieeeeeee gradient estimation. At the W-th iteration, peroth-order stochastic gradient with coordinate-wir wise gradient estimation uniformly randomly select sample index i, from [n.) and then update parameter wi by:
W++1 W/ are Vd f( 2s.)
(12)
where {ar} is sequence of positive step-size and İ f(w,, 24, denotes the coordinate wise gradient estimation form ( We separate the generalization error bound of ZO-SGD with coordinate- wise gradient estimation into three different cases and get the following theorem.
Theorem 3. Assume that the loss function f(; is 3-smohth and L-Lipschitz for every z. Let T be the total number of iterates of ZO- with coordinate-wiis gradient estimation and for any t S T,
if each f(, 2) convex, a, I and choose μ S dn then we have Egen
Σt= ax-
efeah f(,22 2) 7-strongly convex, 0n 1/8 and choose μ e. then we have Eyen
21 20eL
7m

---

Published as a conference paper at ICLR 2024
the the loss f(;2) (0, for all at S for some (fixed) C. >> 0, then have
1 1 aC (2CI2 pOtx (ET))
sC
Cgen
n
Both 1-point and 2-point gradient estimations lead to new expansive factor, which invalidates the contraction property induced by the expansive factor ni of first-order update rules under convex and strongly convex conditions. As result, the generalization bound under convex and strongly convex conditions of the same order as that under non-convex conditions. As a comparison, coordinate-we wise estimate does not generate new expansive factors, and the 01, it brings is also independent of the dimension d.
Remark 1.
4.2 ZO-GD GENERALIZATION ANALYSIS
ZO-GD with 1-point Gradient Estimation. At the 1-th iteration, zeroth-order gradient descent with 1-point gradient estimation updates parameter Wt by:
W
W/ 0t V (D(w));
(13)
where V RD (wr) denotes the 1 1-point gradient estimator of form equation
Theorem 4 (Nonconvex). Assume that the loss [( z) E [0, 1] is L-Llipschitz and B-smooth for all = E Z. Consider the update rule Eq.equation 13 with T the total number of iterates, 04 S C/t(B((T) 1) +AAa/p) p)) for some (fixed) C > 0 for of ZO-GD with I-point gradient estimation is bounded by Egen I min(C + 1, C (og(( + (ET /(n3).
for all S T. Then the generalization error
ZO-GD with 2-point Gradient Estimation. At the t-th iteration, zeroth-order gradient descent with 2-point gradient estimation updates parameter wt by:
W1+11 = We a, V RD(w),
(14)
where v/c (we) denotes the 2-point gradient estimator of form equation 6
Theorem 5 (Nonconvex). Assume that the loss f(,,)) j0, 1] is L-Lisschitz and 3-smooth for all E
Z. Consider the update rule Eq. equation 14 with T the total number of iterates, 04 & C/ (T) + t. for some (fixdd) > and for all S T. Then the generalization error of 70-GD with 2-point gradient estimation is bounded by
(2 + c) CB minf (ET)
CB B
,Clog (cT)).
Cgen
n
ZO-GD with Coordinate Gradient Estimation. At the t-th iteration, zeroth-order gradient descent with coordinate-win wist gradient estimation updates parameter w; by:
Wt++ Wt v (D(w)):
(15)
where (D() denotes the mordinntee-wist gradient estimator of form equation
Theorem 6. Assume that the loss function f(;;z) is 3-smooth and L-Lipschitz for every z. Let T be the total number of iterates of ZO-GD with coordinate-wist gradient extimation and for any S T,
if each f(,22) 3) convex, a $ 3 and choose μ S c. then we have Egen S (2t. (2822
ΣT= On-
eacch [(,, 2) is 7-sttoogly convex, a₁ and choose p Ln then we have Egen
2L
7
if the loss f(-,2) [0, for all z, at S C/ttfor some (fixed) C 0, then we have
(2+ c) (eT) C3 min c3+1 Clog (cT)).
Ggen <
7

---

Published as a conference paper at ICLR 2024
4.3 ZO-S SVRG GENERALIZATION ANALYSIS
In this subsection, we will analyze the generalization bound of zeroth-order stochastic variance reduced gradient method. To the best of our knowledge, there are multiple versions of ZO-SVRG. In the paper, we consider the single-sample version of the 7O-SVRG. Specifically, in the s-th stage, 1-th iteration, ZO-SVRG uniformly randomly selects sample index ii and update parameter wi by
v (wf, =2.) V f(""" 20;) + RRD(")), wi+1 = w acti:
(16)
where i w is the final iterate of stage 1, where number of steps of each stage, and {ar} J is sequence of positive step-size.
ZO-SVRG with 1-point Gradient Estimation. We first consider the generalization error bound of ZO-SVRG with 1-point gradient estimation. Let V fww. 2gg) Vf( z4.) and VRp("*) be approximated Eq.equation and update parameter wi through Eq. equation 16 Then, we have the following theorem.
Theorem Assume that the loss function f(; is B-smooth, and L--Lipschitz for every 2. Suppose that we run ZO-SVRG with step sizes at S C/(ssm((()) +1) LAe)) )) for T steps. After stages, ZO-SVRG satisfies with Egen I (2L2 + BL)S3C exp C/(CBn).
Then we consider the generalization error bound of ZO-SVRG with 2-point gradient estimation. Let V fw zg)). ff("", Zez) and VRD(w" be approximated Eq.equation 6 and update parameter wi through Eq. equation 16 Then, we have the following theorem.
ZO-SVRG with 2-point Gradient Estimation.
Theorem 8. Assume that the loss function f(;;2) is B-smooth, and L-Lipschitz for every Suppose that we run ZO-SVRC with step sizes a₃ S C/ssm (T' + 1) for T steps. After S stages, ZO-SVRG satisfies Egen S (21² cL)saBC exp C3))
ZO-SVRG with Coordinate-Wil Wise Gradient Estimation. Then we consider the generalization error bound of ZO-SVRG with coordinate-wist gradient estimation. Let f 24;), f Zgz and RD (w*) be approximated Eq.equation 7 and update parameter w through Eq. equation 16 Then, we have the following theorem.
Theorem Assume that the loss function f(;=) 3-smooth, and L-Lipschitz, for every z. Let be he total number of iterates of ZO-SVRG with coordinate-wise gradient estimation and for any 1 T,
Suppose choose at S C at state S. After S states, 70-SVRG satisfies uniform stability with Ezen S $2..2 c3)S38C cxp CB/(CBn).
if f(;,)) is convex for all stability with Egen S min {C + 8- clog(e))( (6I? + +3LL) (eS)28C) 28C /n.
C stage S. After S stages, ZO-SVRG satisfies uniform
if 2). is y-strongly convex for all 2, at I 1 stability with Egen (6ST.2 + 3c5)/ (ny))
8 After S stages, ZO-SVRG satisfies uniform
Remark 2. Utilizing full-batch updates with ZO-GD and ZO-SVRG, it's possible to adopt the same step size as in ZO-SGD for first-order updates. Furthermore, under the condition of selecting a smaller step size, the generalization bound of Z0-GD, O(T3C /n), is looser compared to that of ZO-SGD, (
5 NUMERICAL EXPERIMENTS
In this section, we assess the generalization errors associated with optimizing nonconvex loss functions using ZO-GD, ZO-SGD, and ZO-SVRG. To primary goal is to verify the generalization errors of different zeroth-order optimization algorithms and different gradient estimators. To achieve this, we conduct experiments on two nonconvex models: nonconvex logistic regression and a two layer neural network.
8

---

Published as a conference paper at ICLR 2024
5.1 EXPERIMENTAL SETUPS
Nonconvex logistic regression: Initially, we examine a logistic regression problem featuring a nonconvex regularization term. The loss function is formulated as:
f(x) -(0==1--
( Σ (ys (oglogo(-00) (-ag x) (1 y:) oa x)) +
1=1
where a, [Rd represents the sample, yi {0,1] signifies the label, (()) Ite and À is
assigned value of 0.5. Neural network: Subsequently, focus binary classification task using a two-layer neural network with relu activation function and binary cross entropy loss. Dataset: For both nonconvex models, utilize the LIBSVM's Australian dataset. We separate the dataset into two parts: 80% for training and 20% for test.
5.2 COMPARISON OF GENERALIZATION ERRORS ON DIFFERENT ZO ALGORITHMS
In this part, we assess the generalization errors of various zeroth-order optimization algorithms using identical gradient estimators. Generalization errors are measured by the absolute difference between training and testing losses. Figure I depicts our results, with each subfigure comparing the performance of ZO-GD, ZO-SGD, and ZO-SVRG under a consistent gradient estimation method. The figures collectively indicate that generalization errors for all algorithms tend rise as the number of iterations increases. Specifically, ZO-GD exhibits the most rapid increase in error, with ZO-SVRG following. As the algorithms approach convergence, ZO-SGD consistently demonstrates the smallest generalization error. These empirical findings corroborate our theoretical results presented in Table
(a) 2-point (forward)
(b) 2-point (central)
(c) coordinate (forward)
(d) coordinate (central)
(e) 2-point (forward)
(f) 2-point (central)
coordinate (forward) (h) coordinate (central)
Figure 1: Comparison of generalization errors of different algorithms. (a)-(d) are results for nonconvex logistic regression and (e)-(h) are results for neural network
5.3 COMPARISON OF GENERALIZATION ERRORS ON DIFFERENT ZO GRADIENT ESTIMATORS
Due to space limitation, we defer the detailed experimental results and discussions of this part to Appendix B.
6 CONCLUSION
In this paper, we introduce a generalized proof framework for zeroth-order optimization algorithms. Using this framework, we establish generalization bounds for ZO-SGD, ZO-GD, and ZO-SVRG with various estimators and convexity conditions. Our findings reveal that employing coordinate estimates in ZO algorithms outperforms other estimators in terms of generalization performance. Additionally, we demonstrate that ZO algorithms can achieve comparable generalization performance to first-order algorithms by leveraging coordinate estimates without reducing the learning rate.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported in part by the National Natural Science Foundation of China (Nos. 62376104 and 12071 166), the Fundamental Research Funds for the Central Universities of China (No. 2662023LXPY005), and HZAU-AGIS Cooperation Fund (No. SZYJY2023010),
REFERENCES
Atlı Güney Baydin, Barak Pearlmutter, Don Syme, Frank Wood, and Philipp Torr. Gradients without backpropagation. arXiv preprint arXiv:2202.08587, 2022.
Albert Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg, A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, 22(2):507-560, 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D) Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pp. 745-754. PMLR, 2018.
Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop artificial intelligence and security, pp. 15-26, 2017.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions Information Theory, 61(5):7788-2806 2015.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (3(4))2341-2368 2013.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234, PMLR, 2016.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. Advances in neural information processing systems, 30, 2017.
Feihu Huang, Bin Gu, Zhouyuan Huo, Songcan Chen, and Heng Huang. Faster gradient-fie free proximal stochastic methods for nonconvex nonsmooth optimization. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1503-1510, 2019.
Kaiyi Ji, Zhe Wang, Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International conference machine learning, pp. 3100-3109, PMLR, 2019.
Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of regression function. The Annals of Mathematical Statistics, pp. 462-466, 1952.
Alexey Kurakin, lan Goodfellow, and Samy Bengio. Adversarial machine learning scale. arXiv preprint arXiv:1611.01255 2016.
Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, and Ji Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order. Advances in Neural Information Processing Systems, 29, 2016.
10

---

Published as a conference paper at ICLR 2024
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.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 17Xi::1000006880 2017.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free Foundations of Computational Mathematics, 17:527-566, 2017.
free minimization of convex functions.
Konstantinos Nikolakakis, Farzin Haddadpour, Dionysis Kalogerias, and Amin Karbasi. Black-box generalization: Stability of zeroth-order learning. Advances in Neural Information Processing Systems, 15:31555-31544 2022.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp. 506-519, 2017.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for -aaeaee--modo------sse--ee- In International Conference on Machine Learning, pp. 20841-20855. PMLR, 2022.
Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang. Stagewise training accelerates convergence of testing error sgd. Advances in Neural Information Processing Systems, 32, 2019.

---

Published as a conference paper at ICLR 2024
A
NOTATIONS
The main notations of this paper are summarized in Table 2
Table 2: Summary of main notations involved in this paper.
Notations
Descriptions
ZO
Zeroth-order
SGD
Stochastic gradient descent
GD
Gradient descent
SVRG
Stochastic Variance Reduced Gradient
Zic
the random sample
D = 221, 2n
the dataset the numbers of samples the parameter of training model and model parameter space, respectively the dimensions of W. respeciveely
w. W
d
f(w)
the loss function defined as f(w; zi;)
Vf
the gradient of f(w; z4,) to the first argument w the gradient estimation of the true gradient V
V
GOO,CO))
the update rules of first-order methods under samples S and S', respectively the update rules of zeroth-order methods under samples and S', respectively the smoothing parameter the stage for SVRG the whole number of stages the number of steps of each stage the random direction vector drawn from certain distribution ID the number of direction vector the population risk and empirical risk based on training dataset D, respectively the whole number of iterative steps
G.0)0%)))
m
U
K
R, RD
T
w;
the model parameter derived SGD after t-th update
or
step size at the 1-th update
the step size the given algorithm and its output model parameter based on training dataset D, respectively the parameters of strong convexity, Lipschitz continuity and smoothness, respectively the base of the natural logarithm
A,A(D)
7, L
e
B COMPARISON OF GENERALIZATION ERRORS ON DIFFERENT ZO GRADIENT ESTIMATORS
In this section, present supplementary experimental settings and evaluate the impact of different gradient estimators on generalization errors and report the absolute difference between the training and testing losses in Figure 2
12

---

Published as a conference paper at ICLR 2024
For all experiments, set the maximum number of iterations be 2000. The batch size of the stochastic gradient set to be 50. The initial learning rate set to 0.01. This rate is systematically decreased every T iterations by factor of y. Both T and are optimally determined through grid search process where ' and 7 are chosen from {30, 60, 100, 150, 200, 250} and {0.6, 0.7, 0.8, 0.9), at regular intervals helps in fine-tuning the learn-
respectively. The adjustment of the learning ing process, potentially leading to more effective and efficient convergence of the model. For 2-point gradient estimator, we also conduct grid search for the parameter chosen from the f2.3, 4, 6, 8, 9, 12}.
20-002 piladacal
20-0002
20-00 peneeaed
20-003 pits mmer)
20-000
20
(a) ZO-GD
(b) ZO-SGD
(c) ZO-SVRG
je
020
CDlone Serstt
20-51 (0-5V1.00ee devie
766
100 106
(d) ZO-GD
(e) ZO-SGD
(1) ZO-SVRG
Figure 2: Comparison of generalization errors of different gradient estimators. (a)-(c) are results for nonconvex logistic regression and (f)-(f) are results for neural network
As illustrated in the figure, the coordinate-wise gradient estimator has smaller generalization errors than the 2-point gradient estimator. Additionally, both the forward and central difference versions of these estimators demonstrate comparable generalization errors.
C PREPARATION FOR PROOF
C.1 SOME BASIC DEFINITIONS AND LEMMAS
Definition 3 (I-Lipschitz). We say that f is L-Lippchitz if for all points u in the domain of f we have (x)) L. This implies that
(S(u) ((u)- Tilu-1 ull-
Definition 4 (5-Smooth). A function
f: R is 3-smooth for all for all u, Ω we have
[IV V [())] < 31|u ol]-
Definition 5 (Convex). A function f : - R is corvex for all u, E Ω we have
f(u) 2 fv) + (Vf(v), v). Definition (7-Strongly Convex), A fffunciion f S2 + IR is 7-strongly convex if for all u, v E Ω we have
f(u) 2 (w)) + (V)(w), v) + 2 Iu -
Lemma (Hardt et al. (2016), Lemma 3.7). Assume that f 3-smooth. Then, the following properties hold.
13

---

Published as a conference paper at ICLR 2024
1. G is (1 + expannsive
2. Assume in addition that f is convex. Then, for any a S 2/B, the gradient update G is I lexxpansive.
3. Assume in addition that f is yy-strongly convex. Then, for a S गें. G is (1 a82
expansive.
3+7
D THE APPROXIMATION ERROR UNDER DIFFERENT ZO GRADIENT ESTIMATION
From Lemma if we establish the bound for (A()) [(A(D")) then determine the generalized error bound for zeroth-order optimization algorithms. And we apply the lipchitz condition on (,,) get
E (WT;2) - f (wf: S WT w411.
So. bounding the limit of E [6T] Ellur w/ is the main task of this work. For zeroth order optimization, Wz+1 G. (wx) wt a.g, (W(+1) then we have
E G. (w+) G (w/) || (w:) Gr(w()
E Go(we) - G.(ww() a, [[ 2.) Gy 24,) - (g(w),, 2 (y(( 21,) < || (w)) -(((ll + a, (1 2.) Gy(wee, 21,) (G(w), 2..) Gy(w/, 2, ))l
| (w,, =.,) - gy 21,) (g(w), 2.,) gy(w// 2,,i)11 constitutes the primary part influenced by the estimator.
D.1 1-POINT GRADIENT ESTIMATION
The formula for I-point gradient estimation is as follows:
(w pukks 2) Uk.
vf(w, 2)
By applying the Taylor expansion there exist vectors Wi. W with 5th coordinates in the intervals (wl(), wil) + nu(h) U (wb)) + fut(), ,w()) (w*(),, w() + wu())) u (w'li) + uu(() w'))..
such that for any w, w/ E Idd we have
E
Sw, 2) &s(w, =)) (VS(w'z)) S =))
K
f (w, 2) - f (w', 2). uk >
<B
K
k=1
+E
VV (w, - V (wo, 2) mA2)
(Vf (w, - V (w', z2)
K
+E
1
2 uk
V2 / 2) un
+
1
4 V 2 (WE 2) ux
2 uk
un
K
K
K
||
E fl (w, 2) - (w',2))
pK
1 K
E [|
E [I (w, - vs (wo, =]|
Σ
uBE
||ux| 113
K
+ BE [1| 122] -| -w--w'l w''l + 3T [||
|1
if (r(())) =0(0)
E
1 1o wIll
+ 2LE [[] + 3
||
if if (C))
14

---

Published as a conference paper at ICLR 2024
D.2 2-POINT GRADIENT ESTIMATION
The formula for central difference is as follows:
1
K f (w +
wun, 2) - f(w paik =) Wk
(mw)
K
By applying the Taylor expansion there exist vectors W We, W and W with jth coor- dinates in the intervals (wL), wili + mruf") (wl)) + uaa wl)) ( (wo() -uuf" w0), ) (ol(), wll) yraf") (w")), w(()) + pul u (w/li) + =uuk w())) (w/)) url w(l))
(1(1), w/()) - uuu)) ) such that for any w, w' E Id we have
E
V (w, (w,, 2)) - (VI((',,)) - Vs( :3)|
1 K
Vi (w, 2) - V. (w', utt) uhe (Vf (w, 2) Vf (w', 2)))
K
k=1
K
-
U/
T 2 (WZ us
+
K
u
2 f ( (W us) un
k=1
K
| T V f (W =) ms) PAk
T v f (W : uss PAk
Uk
uk
K
k=1
1 K
$
u 12 E f f (1
Vf (w +
Σ
uBE
||
K k=1
1=1
[BB
[||u
[|
wlll
+ nBR 191,
2LE
+
#BB
[1| [|=],
D.3 COORDINATE- WISE GRADIENT ESTIMATION
The formula for forward difference is as follows:
(s(w) I (w + pe,, 2) - [w, z)
11
By applying the Taylor expansion there exist vectors W and W with tht coordinates in the intervals (w, w + μe,)) and (w', w' + ue,). respectively, such that for any w, w e Rd we have
E (V[ 2) mm(,, 2)) (V)(w/,)) 7l(w(, =)|||
d
/ a 2) - v (10,, /4) (w, x) - v (w', x)) ||
eill + 11
c v ʃ (W es eill-
2
i=1
For Ed (V/ (VS (w,
v :)), we have
15

---

Published as a conference paper at ICLR 2024
(V((w, 2) - ff(w, 2)) (VS(ww',)) - (f((((
d
2
4
| (W; )))s) eill +
Σ
2
V / (W: ex eill
==
2=1
<
d3p.
The formula for central difference is as follows:
[w + po;, - -f(w pos, e,
f(w))=
1
By applying the Taylor expansion there exist vectors W W W and W with j coordinates in the intervals (w, w + pez) (w pei, w) (w', w' + pe;), (w ues, w respeecccy,, such that for any w. w' E Rd we have
E V (w, - Vs(W, -V - =()=
(w, 2) (/ /4) V z)) |I
11 e, V f (W; 2) 2) cill Σ
4 V2 f (W7 2) e.) esll
1
4 c / (W, ,w," 2)))) will +
Σ
I / (W .2) es) eill
4
For El= i=1 (VS 2) - ( Vf (w', 2). we have
( 2) - fmm, 2)) - (V Vf(w', (((((,))) =]){|
E
ct 22 2) 2)e; 4:ll
Σ
14 C (W; e)) eill
4
4
iml
[L L (w. 2) aill
+
[ V (w.* =) =)c.)c))) cill
< d3p.
Comparing 1-point estimation, 2-point estimation with coordinate-wist estimation, the increment brought by the last one to the analysis process is d8p, which can be directly controlled by the smooth parameter y and does not bring any associated increment of ///ww' ||. It brings smaller approximation eиrors and does not bring new increments to the expansive factor, so that the generalization bound will be affected by the convexity of the function.
E PROOF OF GENERALIZATION ANALYSIS OF DIFFERENT DISTRIBUTION
The components about direction vector encompassed within the approximation error are defined as follows: C2 á [ 3 Aa e E [[|ا]||]] and 1% A E 1/2 Σ (Y, u)) Uk v/ [v. We can
summarize the information in the following table.
16

---

Published as a conference paper at ICLR 2024
Table 3: Summary of main distribution involved in this paper.
Parameter
Unif( Vd 21Rdd)
Unif
V
Standard normal
4+1
d-1
3d
K
Ad
+2
Vd
vd d +
d+I
Ca
(d 2)
d=
(d 3)
2+3
E.I PROOF OF UNIFORM DISTRIBUTION
E (1,2.... K} be ii.d Unif( /d+ 2B4) distribution. For every random Lemma 7. Let un E KR
vector V E Rdd independent of all uk, h E (1,2..., K} it is true that
1
d2 + 2d
E
ux) wk V
S
VI|.
K
K
Proof. For fixed V E RRdd we have due to independence
K
K
V un) v/
V, uk uk v
K
K2
K
IE
(1 un} ur - V11²
K2
1
(V, u1) 21 v1[
=
E
K
Now, again due to independence
E (VV un)
v|[
E [VV u1) u112 - - -( un) u1 V) [[]]]]
E ((V, u ) 1ll1 [2
2E V mn) (u), V) + |
VT I u | 11
V -VV 4 L + |
s (d+ 2) VTV 2| 1/2+++1 + 1|
= (d+ +/]
Therefore,
1 K ux) uk v v1
(d 1
R
Ev, (V,
K
Thus, is random and independent of all un 's, it follows that
V uk uk v V
V up) us - -v IV
E
E
d +
|
K
17

---

Published as a conference paper at ICLR 2024
d +
[
K
and our claim is proved.
Lemma 8. Let RR E (1,2..., K} be i..dd Unif( (dst-1)
distribution. For every random
vector V E Rd independent of all uk, f1,2..., K). it is true that
uz) uk v
d
B
ug) V
v
IVII
K
K
Proof. For fixed V Rdd we have due independence
K
K
us) us v
ukk
UA
V
K
K
K
IE'
(I(V, un} us - V12
K2
E
[I u1) u1 V
=
K
Now, again due independence
(V, u1) 01 v = E (V, u1) u1ll 2 2 2((V un) un V) + [
E ((V, =² 2 || |2] - 2E KV un) (u), v) + ||
V'E f || | V 2V [n1i] V + |
Vv |
(d-1))1 V|
Therefore,
1 K
V un) us v
(d V-]
E
Σ
K
K
Thus, if V is random and independent of all ug 's, it follows that
K
uk) uk v v
E
E
V
up) uk V
IV
d
V
K
d
[V].
K
and our claim is proved.
Lemma 9. For samples u from the Ez-sphere, it is clear that ||u]|2 Vd and |/ då, When ~ Uniform (Bd). the density p(t) of [|2]]2 is given by d tdt 1, consequently, for any we have
18

---

Published as a conference paper at ICLR 2024
E [ = L. t'p(t)dt - ( eatte-l dt d+k
Lfo
Thus for Z Uniform (Vd + 2B²) we have EE [1 (d (od++)) 2/ k))
F PROOF OF ANALYSIS FRAMEWORK
Proof of Lemma 3 Let D, D' be two samples of size n that differ one sample, and let C.()), be two update rules of zeroth-order algorithms based on samples D, D' respectively. Under the event & = (G-()) = (.)-)), we have
4+ =E|(G, (wx, - G (wf) || E. (wr) (w((i)
=E|[G((w]) Ge(w() + 0n (5(we, 25.) 9y(we; 21,) - (g(w), zi.) 9y(wl, =x))] ((1))22)) 2.,) (g(w/), 21,) Gy((u/y 21))
< ||G₁ (we) - Gr(w))]] ar [[g 2.) - gy(we,
Sy|lwr w/ll + a, [|g(w,, 21,) Gy(we, 21,) (g(w') 21,) - Gy(w/, 24,) ))
<y/lus w/(l 04
The Under the event =
= (ā:()) + C(()), we have
ElJå, (w.) (w())l II
(w:) - G((w()) at [g(ur, 21,) gy(we: 21,) (g(w)) 24) 9y(w/: ( +(,)]
< |[G; (w:) - G((())l + a [[ 24,) - G,(,, - (g(wl,,2)) - 9y(w0,, )|
< min(n, 13 1| w/ll + 20, + a [ (w,, 21,) - gy (1) (g(w,, 24,) - gj (wh, (w)) <|Iwe -w'll + 20; + a |g(ur, 2.)) - gy(we, 2.,) (g(w), 24,) - gy(w/, (1,))
<|(we- ww'll + 2,,0 + 4,013
Proof of Lemma 4 Consider the events & A { () = 6 and &f & {Gil) + c.)) (see Eq. (4)). Recall that P (E,) 1 1/n and P (Ef) 1/n for all S T. For any to 2 we have
18 [ -P(E))B(0+++ EE,, Ese, + P(E))
Esrg
=(1 - 1 BB(o++1 E3 Edro 1 + E[8.+1 1E%, Esrol
1
1 n
1 220 2 + a1a)
< (n + -(1 (1 1) 1)) 1 + ar (1 Jo,,
n
Then have
[ <
Σ
T
n (
T-t
(1 - 0o,11 + - (20r, + +0.)
t=t+1
G PROOF OF GENERALIZATION ANALYSIS OF ZO-SGD
G.1 ZO-SGD WITH I-POINT GRADIENT ESTIMATION
Lemma 10 (Growth Recursion). Assume that for all f(,,2) is L-Lipschitz continuous, 3-smooth,
1" and { (ci) T Let wi = w/g be
and f(,2)) E [0, 1]. Consider the sequences of updates { (G [ 1=1
t=1"
19

---

Published as a conference paper at ICLR 2024
the starting point, w1+1 G. (we) and w/41 0i (ux)) for any t E fl....,TY, T). we; w// R.d and 2 0 the following recursion holds:
Then for any
{ (n + a1 aaB (Tá +1 + ocLAa) |10, w/ll + CBarCa.
- (0(()=((1 if,(() + C)()
E G (w,) - ( (wt) (w))
- ||we - wi'l + ande + 20, + 1) + pBarCaa
Proof of Lemma 10
The formula for 1 1-point gradient estimation is as follows:
I [w + puuk)
Vf(w)=
Uk-
P
Let S and S' be two samples of size n differing in only a single example, and let G.) (.) be the update rules of the ZO-SGD for each of the sequences S' respectively. By applying the Taylor expansion there exist vectors Wa, W with coordinates in the intervals (wf)) wo + + U
R3
(w.") + +nU k,t. (
(i) , wit + +uU u (we (()) + k,t, + wz m
) such that for any wr, w/ E
Fd we have
cl (w;) - -Ge (wx)i]
E
<
|| (wi) - G¹ ('(will + t
(Vf(w))) - -f((w)) -Vf())) +)(Dا)|
1
I (wx) - S (wf) uf >
S (wx)) - G² (w'ill + az
K
11
k=
K
Vf (w)) - Vf (wof) uxb u - (w;) - Vf (uf)))
+ai
K
k
+0+
K
2
T k
mn
(W ux2 u
+
K
1
p u
2
V f (W utz 2/
k=1
k=1
|G (wi)
- G¹ (wiil
+
|IV (w)) - vff (w/)ll + at
E | E V (w)) - vf (w/))
04 K
||
+
Part A corresponds to the first-order stochastic gradient descent (SGD), which decomposes into and ør, terms. Part B corresponds to the scaling term introduced by the gradient approximation. which leads to inflation factor 1/' and bound factor. In contrast to the 2-point estimate, one-point estimate has an additional term Part B, which generates different expansive and bound factors. should be noted that the term appears in the denominator, so its value needs to be carefully chosen and not too small. Part E corresponds to a fixed value that can be decomposed for both one-point and two-point estimates, and can only be constrained by 8-smoothness, finally added to the bound factor.
Under the conditions of L-Lipschitz continuous, 3-smooth, J(, E [0, 1). E [|U1]]] S C.. we get acda + 2ox LT + 1BaCss P
v/ = kT d + L.A. ar1 1aBayCa 0t2 -., 01,3
Lemma 11. Assume that the loss function f(;,2) 2) is T-L-ipschitz and 8-smooth for all Z. Consider the ZO-SGD algorithm with final-iterate estimates Wt and W/p, corresponding to the data-sets S, S', respectively (that differ in exactly one entry). Then the discrepancy öT _ I|Wr W7ll, under the event Es.r. satisfies the inequality
E [r ES.0]
20

---

Published as a conference paper at ICLR 2024
2L (T' + 1) + a,LAd
+ MBCa
Σ at
T
II
T
(1+ + 1) ayLAs
pn
P
1=
j=t+1
Consider the events & _ (G(()) { and & - (G,()) + (.()) (see
Proof of Lemma 17
Eq. (4)). Recall that P P(E.) 1 1/n and P (Ef) 1/n for all S T. For any 4. 2 0, direct
application of Lemma gives
E
16e+1 E
=P P (E,) E [8c41
Ec, Eo,ol
+ IP (E E Es
+ -B [0c41]
E [oe+1 | Ee, Eniol
Eg E8io]
(1-1
1 n2
acLind
204 (T + 1) +
aLAd
< + (T +
+
IR Jo
Eb.0l
+ 1BarCa-
um
then by solving this recursion we have
E bT Ebrpl $
2L (2
(T +1 + 13Ca
Σ 1=
T
T II
1 (1,,8,(T3 +1) (1- n
+
a vyLAA
s=++1
Proof of Theorem 4 Recall that 17 1 + 3a, for general (nonconvex) losses
Assuming that
at S C/t for all t t T, we have
E [5r
E
2L
Ad um
[1-a +1) 2yLAs
(T + 1) + MBCa+
Σ
II
71
1=t++1
j=t+1
2L
Ad
T
T
CB(T + +1) + CLAc 1+
<0
(I + 1) + HBCa+ +
um
1=
j=++1
j
<C 22 (I + 1) + 4BCa +
2L
Ad
T
T
C3(T + +1) +
CLAr
exp
j
1=t+1
/=(+1
SC(ET)) +1)+ cLds
22 n
NBCa + Ad
Σ
1
um)
(t +1+1) C +1)+ CLAA
1=to+1
B(rK +1)+ + LAa) -1
2L
r + p3Ca+ +
Ad
ETT
Ca(T +1)+
CLAR
CBC +1)+ CLAA
n
pm
We define q A CB + 1) +
CA.
and find the value of to that minimizes the right part of
to
< to
+ LD (
(eT 4
Elf (Wr, - f (W+, ]]]] < u,z
sup fw, 2) + LE [ōr Eonn]
69
to
which is to min ((gnI.D) 1/.TDD)/lo+l))) (c (/T// T}. Then we give
Elf 2Wr,2) - f 2)
(qnLD) - - (f 1+1/ (eT) (ET)
< max
LDe
carr 41)4 CLAd
1 CB(+++1) CLAz
2T. +1) 13C.TI A&L
cairk +1)+ eLda
(eT) CAC ozdy
21

---

Published as a conference paper at ICLR 2024
c CLAA carr CLa4
1
+1(+++1)+
eLda
- CLAa
2TT + 1) + CBL+
AaL uVn
carr 1)+ مLda
n
Cart-11 CLAi
10
CL )
CLAd +1)
corr +2)) Chida 12 (eT) ca CLds
1+ 18
CB +1)
PLOVE
1+ +0+ + CL
Te 11/e
Theorem 10 (convex). Assume that the loss f(;,)) E [0, 1] is L-Lipschirz, B-smooth and convex for all E 2. Consider the update rule Eq. equation 10 with TI' the total number of iterates, at S C/t for some (fixed) C > O and for all t < T. Then the generalization error of ZO-SGD with 2-point gradient estimation is bounded by
Egen I (1+)))))) (1+ (2 c)CL) 3Te/2m.
Proof of Theorem we have
10
Recall that 1 for convex losses Assuming that S C/t for all t S,
E
|8T|
2L <
Ad
T
T
(1+ + ayLAd
(TK + + p3Ca +
Σ
II
an
umn
1
tmto+1
j=1+1
C CLAA j
2L
Ad
<0
(T + 1) + pBCa+
II
1+
n
pm
t=ta++1
j=tt1
22 <0
Ad
T
CBr
+ CLAd P
- (T + 1) + PBCa +
exp
um
I.
Car CLAs 2L (T + 1) + 4BCd +
Ad
Σ
T
1
um
t
(t 1) CarK CLAS
t=to+
Car CLAR
LAa
2L (Tk + +1) + 333Ca +
Aa
eT
car + CLAA
<
gT
11
un
to
We define q 2 CBT +
CA. and find the value of to that minimizes the right part of a
E1 (Wr, - (W4, =)1 v to
to
+ LD (
[eT 4
sup swn, =) + LI [8r
Ed,
69
w.z
which is to min (latt) TT. Then we give
E Elf (WT,2) 2) f 2)]
(D (cT) 1+
(- (ET) LDe
< max
n
n
1 1 Car + CLAd
car CLAA
AsL /
cark CLdR
(eIT) cark ozda
2L 2I +1) 43CamL+
cark CLAg Car Cata
CLAA 1 + C + 1
cark CLAR+1 n
(2T,(T))) + +1) CBL A&L p/n
cork CLAi +1 (eT)
1
22

---

Published as a conference paper at ICLR 2024
cerr CLAy (eT) card CLd
1 1+ 3C +
CL
1
C
CLAd
+1
cark CLdd
TLOVVR
1
1+ 30+ =
Te Te/+
Theorem 11 (strongly convex). Assume that the loss f(.,2) [0, is L-Lipschitz, B-smooth and y-strongly convex for all z E 2. Consider the update rule Eq.equationn 10 with T the total number of iterates, at I C/t for some (fixed) C > 0 and for all S T. Then the generalization ervor of 2O-SGD with 2-point gradient estimation is bounded by
Egen I +1+ (1 (2)c) 8Te/2n.
Proof of Theorem 77 Recall that 7) =
a:91
for 7-strongly convex losses B4y
Assuming that
Ot I C/t for all < T, we have
E |or|
E
2L TT +1 p3Ca +
Ad
Σ
II
T
(1+0,
7
aq ayLAd
On
jum
3+7'
11
#=(+1
2L
Ad
T
C
CLAA
<0
- (T +1) + MBCa+
1+
pm
j=l+1
2L (T + 1) + MBCa + sc 50(2
Aa
T
T
CBT + CLAd
exp
pm
t=
j=t+1
<C(eT) C8T CLAS 2L
(2
(T + 1) + u3Cd +
Ad
T
(t 1) car CLA
n
im
t=t++
|T
LAd
2L (2L (Tk + + pBCa +
Ad
eT
Cer
Clda
cark + CLAA
1
um
to
We define q A CBTK + CAe and find the value of to that minimizes the right part of
Ilf (Wr, 2) - f (W4, 2) v to
to + LD
( cT 9
sup f(w, 2) + LE [8r Edrg9
6d
w.z
which is l7 = min ((m 1/0++1)(1100))))) ( (eT) T}. Then we give [l (Wr,2) 2) - f (W,,
(qnLD) - (eT)af 1+1// (ET) LDe9
(fT)
< max
car + CLAs
1 CATK CLAR
AsI.
cart bLAR 11 (cT) car ord x
2T +1) 4BCamL++
n
car CLAR
1 + CST + CLAY
Cark o1.
222(1' + +1) +1) CBL+
A&t Pyn
cark CLAS
(eT) cpr + crck
cory GLA1
1+ 30 + CL -1
CLAs +1
cark CLdRes +1 (eT) cark onda
<
CBNV
TLLOVE
23

---

Published as a conference paper at ICLR 2024
s ++ 3C )
Te T/le
PLÖVE
G.2 ZO-SGD WITH 2-POINT GRADIENT ESTIMATION
Lemma 12 (2-point ZO-SGD Growth Recursion). Consider the sequences of updates { (a:) {ci) t-1
T
and G t=1 t t (I...., TT. Then any wi, w/ E gd and t 2 0 the following recursion holds
Let we w/g be the starting point, W1+1 = G2 (wx) and w/++1 =G² (w/) for any
(m + a (1) I| - will + Cd
if, [ G) +
E G (wxx C% (w)i) -
I|w, w''l + 20 (Ta + 1) - Ca
Proof of Lemma
12 The formula for central difference is as follows:
f((w)= 1 f (w + +mwx) f (w patk) K
Σ
Up
2p
Let S and S' be two samples of size n differing in only a single example, and let Gr(.), Gi() be the update rules of the ZO-SGD for each of the sequences S, S' respectively. By applying the Taylor expansion there exist vectors W W W
vals (w)") we (3) + (U kit J ot ( + +pul) R u (1) k.t and W
Ret with 5thh coordinates in the inter- w () pl
R wl() w ... (u wn( uu 1 U u (b) + nulh kot w ( (1c puli (1))) U w
kit
(w,t) un (1) + nU(t)) k,t
(6), wi(h) v1 k.t
k.t
such that for any we, wt E Rd we have
Go (wr) - G. (w/)
$ ||G (wr) - G" (w/)ll + 0z
- vf(w))) - -
(VS((() {((WاT)
< ||G (wx)
G² (w/il + ar
V/ (wr) - v. (w/))) ) .1ht u/ (V/ (w:) VJ ((()))
K
1=1
1 K
+0
" Uk
T (orf(WW (WE.)) wa)
ui
+ +
U
V
(WEe) ui wi
K
K
K
k
+
Σ
4 uk
V2
( ub²
uh
+ +
Σ
V
(wzz)
ute)
K
K
4
1=1
k=
<w;)
G¹ (w/)]
+
+arl
| (we, 21,)
Vf (w/r Ziz Ill
+
[|
K
1=
E
Part corresponds to the first-order stochastic gradient descent (SGD), which decomposes into r7 and 0t22 terms. Part B corresponds to the scaling term introduced by the gradient approximation, which leads to a new inflation factor r)' and new bound. Part E corresponds to the irreducible term caused by the difference between the estimated gradient and the true gradient, denoted as 0t, Under the conditions of L-Lipschitz and 3-smooth and E || ||] < Ca. we get n/ a, y, σt.1 paBo.Ca.
0,2 L, Ft, 2a,LI 4.aCa. Thus the expansive and bound are the same as the forward difference results from the previous work, thus their generalization bounds are also identical.
24

---

Published as a conference paper at ICLR 2024
Lemma 13. Assume that the loss function 2) is L Lipschitz and 3-smooth for all Z. Consider the ZO-SGD algorithm with final-iterate estimates WT and W1, corresponding to the data-sets S, S', respectively (that differ in exactly one entry). Then the discrepancy dT _ ||Wr W4 under the event En.g' satisfies the inequality
T
22 (T + +1) + pBCa)
E frr Eor0l
Σ at II (1+ Ba, + +1) 1=o+1
71
j=t+1
Proof of Lemmal
13 Consider the events & - (G(()) { and &f - (G,()) + (.(()} (see
Eq. (4)). Recall that P(E) = =1 1/n and (EE) = 1/n for all t I T. For any to 2 0, a direct
application of Lemma gives
E [0c+1 Edr0] = P (Ee) E [8e+1 & Eo00] [ P(E)) E [óc-1 E Es
E [ōet1 Ee, Ehiol
+ E [8e+1 Eg En1ol
n
n
1 (1- (n E [ōr Edig! + 2acL (T 1) + pBanCa-
n + Tn n
then by solving this recursion we have
(2/ 2L (T) 11)
1+ Bay + +1) 11 (1-
E frr
Eoio]
P3Cd
Σ an II 1
n
/=1+1
Proof Theorem? 2 Recall that 17 1 + _a, for general (nonconvex) losses
Assuming that
Ot I C/t for all t _ T. we have
T
E
(8
EGral
2L ( 1) + U3Ca
Σ
a II
(1+ 1))
1lo+1
f=++1
$ C
2L (T' 1) + 1BCd
Σ
T
T
1+ CS(T) +
5
1=
j=(+1
(2L (Th 1) + 13Cd
T
C3(T
SC
Σ
exp
j
1=to11
#=1+1
2L C(
(Th + 1) p3Cd
Σ
(t+ ()((()))
n
toot1
CB(T++)
(8(T +
2L
r + 1) + H&Ca
- - 00(
We define q A CB 1) and find the value of to that minimizes the right part of
tg
s Lo
(eT
[I 2) - (W,, 2)] <
sup [w, 2) LE [ōr Es,,,
+
LD
n
n
to
Then we gives which is t min (gn //( (cT) ,T} and n3C,
r
E [If (Wr,2) 2)]
(gnLD),+ (ETT) of 1+ 1/9
(eT) LDea
< max
n
25

---

Published as a conference paper at ICLR 2024
ce(r3++) ((2 (2+ c) (T++1) + +1)+ ca(r)+1)=1 (eT) ca(
1 (3(t))1)
3Te
$ (1+
2n
Theorem 12 (convex). Assume that the loss f(,, E [0. 1] is L-Lipschitz, 3-smooth and convex for all Z. Consider the update rule Eq. equation 7 with T the total number of iterates, at S C/t for some (fixed) C > O and for all t S T. Then the generalization error of ZO-SGD with 2-point gradient estimation bounded by
S ((C))))-)) (1+ (2+ (2+))
Egen
Proof of Theorem we have
12 Recall that 7 for convex losses, Assuming that 0r S C/t for all t S T.
E
[8r
Eórol
- (T + 1) + UBCa)
2L
Σ
T
a
II (1+
1=
1=++1
2L T 1) + H3Cd
Σ
T
CB(T + 1)
0
1+
11++1
j=(+1
<
2L
(T + 1) + UBCd
T
II exp
CB(T +1)
j
100+1
j=++1
2L c((T))
- n
(T +1 (lBCaa
Σ
+
1)(((1++1)
(=o+1
((2))
CB(T++1)
< (0r
-1
2L
1) + mBCaa
(ee
-0000-11
We define q - CBT and find the value of ln that minimizes the right part of
[II =) - / (W4, =)1l S to
to LD
[TT
sup s(w, 2) LI [ōr Esi n
+
E9
n w,e
to
which is t min ((onLD) (ommLD)//(0+0) 1/00 (TTa//a+1)))))) T) and
+1 n3C,
Then we gives
E [If (Wr,2) (W/,
(qnLD) ने. (cT) मे. 1 1/9 (qnLD) (cT) गंं LDe
< max
n
1 cS(1++1)
cocrt+1>
((2 (2+c))11 CTT (Th + corrgti)t (eT) epery
n
3Te
< (1 + (BC)- (1 (2+ COL3)
2n
Theorem 13 (strongly convex). Assume that the loss f(.,2) E [0. 1] is L-Lipschitz, 3-soooth and y-strongly convex for all z E Z. Consider the update rule Eq. Eqq.euutioon] 71 with T the total number of iterates, at < C/I for some (fixed) C > O and for all < T. Then the generalization error of 70-SGD with 2-point gradient estimation is bounded by
Egn (1+ (1C)-11)) (1+ e)CT.) 3Te/2n.
26

---

Published as a conference paper at ICLR 2024
Proof of Theorem 13 Recall that 7)
a.9r Bty
for y-strongly convex losses
Assuming that
0t S C/t for all S T, we have
E [8r Eórol
21. (T 1) UBCa)
Σ
a II
(1+ 87,²)
t=to+1
s=1+1
21. (T +1 + H3Cd
T
(1+
Σ
II jitt1
1
22, (Th + 1) + U3C2)
T
T
CB(T
$ C
Σ
II
exp
t
j
(=t+1
jmttl
s C(eT))BITi+1)
(2h n
(r+ + 1) + +PSCa
(t + C)
t=o+1
2L (r + u8Ca) s (er -1
eT
cB(
To
We define q C d and find the value of to that minimizes the right part of
(W4, =)1 v to - -) (WT,,
sup s(w, =) + LI [ōr Esrol S to
(eTT (eT) 4
+
LD
69
to
which is 17 = min ((ont) T} and S
+1+1 n3C,
Then we gives
E [If (Wr, =)]
(gnLD) (ET) गो. 1 1//
(g LDea
< max
n
n
+ c3(
coark (2)
(2+ c)CL' (T2 + 1)) 3Te
+acr/+1) (eT) cair++1+1
n
< (1 + (1
2n
G.3 ZO-SGD WITH COORDINATE-WE WISE GRADIENT ESTIMATION
T :-1 and (G: (oi),, Let wo = w/ be the starting point, Wt+1 G2 (w:) and w/-11 = G¹ (w() for any t [L....,T}. Then for any we, w/ E Ed and t 2 0 the following recursion holds
Lemma 14. Consider the sequences of updates { (cr)
E [1 (wr) - 06 (wt) []
S (n) |1w w/ll + asudd,
=
||we - w/ll + 2a, L + anudd
if # G(()).
Proof of Theorem (onvex). The formula for coordinate-wise estimator is as follows:
Wi+1 Wt az
i=1
e [witper, -/w )er
P.
forward difference,
e; central difference.
2p
Let S and S' be two samples of size differing in only single example, and let Ge(+), G.(()) be the update rules of the ZO-SGD for each of the sequences 5, S" respectively. By applying the Taylor expansion there exist vectors W and W.,, with th coordinates in the intervals (w,, we + pes) and (w/, w/ + pez), respectively, such that for any Wa, w IRd we have
27

---

Published as a conference paper at ICLR 2024
Gc (we) G/ (w/) || = ||Gr (wr) - G. (w/) ||
= =Ilw8= - -w'g- 0t
f (wx, zi,) - Vf (u)) 21,, ,e,) ci
T 2 ( 21.) es)
Gs + 0 Σ
-
- (W 1 es) esll
04
;
+
||
ai S (wy; 21.)
(10k
04 VS (10/s 21:))
w= a) a))s
V (uc, 2iz w= 8) es + Ctt
oi
d
Σ
( f (w0,, 2z ) - V/ (w/z 2i,,, ea) Es
(VI (we, zz.) - vs (w/b mn,1) II
-[:((w:) G (w() ar Σ
VoT Vul (w, 21. \ ei
2
==1
+ 04
1 T
Ci I (w. Ziee
w= 8i) eall-
For >
(V/ (w,, 2i.) v (w/, ; e, VI (wi, - (.f,,, This is the key, why
ZO-SGD using coordinate-wist wise estimator is non-expansive. The last display and the triangle inequal- ity give
E [| (wx) - G. (ut)
uB 2
$ || (wx) G (w\i)l + 20,
Σ
E
[Ie:1]"]
< ||G (w:) G (w/)3l + adp3dd
Above all, coordinate wise estimator
Let S and S' be two samples of size differing in only a single example. Consider the gradient updates GI...., GT and Gi....,G",, induced by running ZO-SGD on sample and S respectively, Let wr and w/y denote the corresponding outputs of ZO-SGD. We now fix example E Z and apply the Lipschitz condition on f(; 2) to get
E Iff (WT;2) - I (w/r; S [6T),
where 87 || w/y ||. Observe that step I, with probability 1 - 1/n, the example selected
by SGD is the same in both S and S'. In this case we have that G, = G² and we can use the l-expansivity of the update rule G. which uses the fact that the objective function convex and that at S. 2/B. With probability 1/n the selected example is different in which case we use that both Ge and G₁ are a, L--buunded as a consequence of Lemma 12. Hence, we have
1 n
1 E 15.1 12
20,L Bar E E[8,] +
20, L + aB
1 S
[6.11 +
+
+ n n2
n
Unraveling the recursion gives
T
2L + 99
E E
at
n
t=l
Plugging this back into equation, we obtain
21.2 + LB
El (WT; 2) - f (w/r 5
0t
n
28

---

Published as a conference paper at ICLR 2024
Proof of Theorem 3 (Strongly Convex). Let S and 5' be two samples of size differing in only single example. Consider the gradient updates Gl...., ..Gr and Gj.... GT induced by running ZO-SGD on sample S and S", respectively. Let wr and w/ denote the corresponding outputs of 7O-SGD. We now fix an example ε 2 and apply the Lipschitz condition on f(::)) to get
E (WT: (w/: =)1 - LE [8y]
-xpannsan With probability 1/n the selected example is different in which case we use that both G, and G., are aL-bounded
If S 1/B: since 20.97
B+7 2 ary and ary S 1, Gr.a is (1
E [6++]
(1- (1- ni
E [. + 11
2aL
par
(1 a1)
20l. 033
n
n
Unraveling the recursion gives
2 + aB
T
2L 2
E [ v
Σ t=
(1 an)' -
n
107
Plugging this back into equation, obtain
212 + 3L
E (WT; - ( S 117
Lemma 15. Assume that the loss function f(:, 2) is Lipschitz and 3-smooth for all z Z. Consider the ZO-SGD algorithm with final-iterate estimates WT and W4,, corresponding to the data-sets S, St. respectively (that differ in exactly one entry). Then the discrepancy bT - 1| - W7ll, under the event Eo. satisfies the inequality
T
2L +
E [
Esro!
uB
Σ
at
II (1 + Bay) f=1+1
1=1o+1
Proof of Lemma 75 Consider the events & (G(() d}(}} and &f e {ā.()) Ci(O) (see
Eq. (4)). Recall that (E,) = 1 1/n and P (EE) = 1/n for all t s T. For any to 2 0, direct
application of Lemma gives
E 18141 EáGgl
= P (Et) |dtt1 Ee, Esng
+ (ET) E [det1 & Eorgg
(1-1 1 E [8c+1 Ee, Edr
1
+ E [de+1 Ei, Esogg
n
< (1 + an3) E Se EErol + 20yL
+ 4Bar.
then by solving this recursion we have
22L
E pT
Es,o]
<
uB
Σ 02 II (1+ Bay). j=t+1
12
t=ta+1
Proof of Theorem 3 Nonconvex). Recall that 1 = 1+3a, for general (nonconvex) losses. Assuming have
that a₁ C/t for all T and μ S e n
T
T
E (8T Esn,l
s (22 + 4B
Σ
II (1+a,8)
at
1-t+11
j=t+1
22 (2L
(1+ C3
< SC
p3Ca
Σ
1+
1=t++1
j=t+1
29

---

Published as a conference paper at ICLR 2024
1 C 2L
+ MBCa)
Σ
T
T
exp
CB
j
t=to1
j=++1
C(
(2L
+ 1B
Σ
T
1
1
n
t
(t
+ 1)08
t=to+1
2L + cB
<<TT)
CB
E
cB
D
We define q 2 CB and find the value of to that minimizes the right part of to
EI (WT, 2) f (W2, =)]l - to
[ef 4
sup sww 2) + LIE [Ōr Enrol + LD
69
wne which is t min {(o 3/ / (eT)) T3. Then we gives E [If 2) f (W', I|
सों + 1/9 (qnI.)) गों (eT)
S max
(gnLD)=+ (cT) LDe"
n
n
+ sC
(2C1? + 3Cel.) शθग (eT) मिना
n
H PROOF OF GENERALIZATION ANALYSIS OF ZO-GD
In the case of full-batch GD and ZO-GD the algorithm deterministic and we assume that 21, :,,.: : Zis...y
Znz 24 are i.i.d and detine S - (21, (2,,...... ... ,
and S' a
(21, 22, ,fp...,Zn)) ,2n) Wn = Wy the updates for any / 2 are
(we- a4 (((,, 1 Σ
W1+11 Wt n
V (wi, 2j)
i=1
1141
w/
Vf Vf 2/)
0t f (w/, 2/)
n
n
j= ii
(w/ at (f(((, 2)) + (w/. at V v((ww(,
(=1,
Then, for any t t 1
1
8141 <
[[ w/) a- (Vf(ur, 2.) v vf(wl, 2])]]
n
i=1iij]
+ 12
(w)= w!) - 04 (Vf 2;) - Vf(ui, =/))
1
min (1, 135, + 2 L
5 n
n0, +
n
L
< nd; +
n
Therefore, for full-batch ZO-GD, we have
v (w,, 23)
W1+1 =W
30

---

Published as a conference paper at ICLR 2024
Wi 04 (ir 21))
(w0, zi)
(wz, zi),
n
2/41 = W
0n
Vf (w/ 2,) - 0t v (w/, 2/))
(=1
(m) - a, V. + (nmz - a Vf((u
π1
1=1
{((w(( + at (vʃ(w/) z5) {((u'), =)))
Then, for any / 1.1
L0
det1 S n00 +
at +
Vf 2)) - f((u, 2:))
Σ
- (ff(2))))(((((2)))) - -/(()/((())))))))
Proof of Theorem Recall that ut are independent for all ks K, tST and the loss function is Lipschitz, smooth and f(-) I 2. The last display and the triangle inequality give
20, + rr
de+1 S n1 +
Σ
[VS(wr, 2.)
VS(Wk, =:)ll
n
n
1=1,1
+ "T [f( 2j)
v f 2/)11 +
As
Σ
[Is 2i) - f(1,, z:)l
mu (=1,%
and
[[((ur, 2z) - f(w/r 2/حll + ac33Cs
nu
< + az
(TT' 1) 3 Aal
) f
81
20,L L (T + 1)
+
Agac np + pBCaar
Then by solving the recursion we find
L (I + 1) +
Aaas
T II jmtt1
(r% + 1) B AaL
# ))
84
+ 4BCaar
(1
nu
Under the choice 04
the last display gives
1( ((TT
Zq4
2L (T +1)
Ad mi
C
T
91+
8T <
+ P3Ca
II
n
(T + +1) B
AoL
s=++1
21 +1)
+ nu
Aa
+ m3Ca
C
9)
(I' + 1) 8 + Ash.
j=H+1
2L + 3 + 3L
C
T
C
Σ
Σ
exp
nBL
[
t=l
j=t+1
2L2 + 3 + 3L
T
C
exp
C'log
nL
[
t=1
31

---

Published as a conference paper at ICLR 2024
C (2L2 + (L)
T
eT
n3L
t+1
(=1
C C (2L² +
1
n,3L
t0+1
(ET) (2L² + 3 + (L)
min + m C'log (cT)).
n3L
Then the generalization error of ZO-GD with 1-point gradient estimation is bounded by
2L + 18+ 3L
Egen I
(ET)) min(C + 1,, Clog (ET)}-
nB
Theorem 14 (convex). Assume that the loss f(-22) E [0, 1] is L-Lipschitz, convex, B-smooth for all 2 E Z. Consider the update rule Eq. Eq.equation 13 with TI' the total number of iterates, on S C/t(B(LT) + +) + LAa/P) p)) for some (fxxdd) C > 0 and for all S T. Then the generalization error ZD with lppontt gradient estimation is bounded by
gon S <min(C + C,C (,CClo(ee))((21 + +
(L)(eT)/((3))
Proof of Theorem 14 Recall that 77 = 1, ut are independent for all ks K. tST and the loss function is Lipschitz, smooth and f(.) S 1. The last display and the triangle inequality give
8.41 S nd; +
201L att rrk Σ
[VS(wr, 2i) v Vl(w' z:)1l + at r | (wr,, 2j) - VS(W,, 2/y
im 1m1li
arAd Σ
azAd [[(we, f(w/, 2/ح1l + asp1Caa
+ mu :=1,if)
[I 2:) - f(w),
+
AaL
)]
20 (r +1)
Agar np
$ + at
B
81
4332ar
n
Then by solving the recursion find
8T 2. (T + +1)
Agoe
(rx3+ )
p3Caar
II
(1+ a
n
nu
j=t+1
Under the choice at
the last display gives
+(TT(+1)0+ +1)0+ Agl
2T (T +1)
Ad tije
C
(1+
8T <
+ p3Ca
II
n
(T + +1) B Aal
s=t+1
(T( +1)
+
Ag + mdCd
T
1
mp
Σ
1+
(TK + 1) 3 +
Azh
1=1
j=t+1
2L2 + 3 3L
T C
T Σ
C
exp
n (ml
t
j
j=++1
2L2 + 3 + 3L
C
cT
nL3L.
t
exp
Clog
1+1
C (212 +B 3++ (L)
T
eT
n,
1+1
32

---

Published as a conference paper at ICLR 2024
C (2L² + 3 (L)
T
1
n,3L
80+1
(ET) C (2L² 3 3L)
min(C + 1, C' Colo (eT)}.
nL3L
Then the generalization error of ZO-GD with 1-point gradient estimation is bounded by
21, + 3 BT.
Cgen S
(eT)) min(C + 1, Cloo (ET)).
nß
Theorem 15 (strongly convex). Assume that the loss [[ 2) E 0.1] is L-Lipschitzz 7-strongly convex, 3-smooth for all z Z. Consider the update rule Eq. eqqutiition 13 with T the total number of iterates, o S CBT(B + 1) + LAg/ ()) for some (fixed) C >> 0 and for all t S T. Then the generalization error of ZO-GD with 1-point gradient estimation is bounded by
minnC + +1,Clog(eTT)(22 + +++ /(3).
Egon
Proof of Theorem
Recall that r) = 1 0,97 u are independent for all ks K, tST and the loss
B4yy
function is Lipschitz, smooth and ʃ(-) S 2.
The last display and the triangle inequality give
de+1 S nde
20
at "Ik
Σ
[V 2x) - vf(wb,,)) 2)ll
n
ag " + 24) V - a,ds
Σ
1f(w,,))) f(w/, 21)l
n
np
i=1,0
+ Ad
([( - -s(wk, 2/حll + acp3Cs
nn
T 3-
By
+ Aat
1 )
200 (I +1)
Agas np
$ 1
as
80 +
+
+ 4BCdas
B 3+7
Then by solving the recursion we find
8T
20cL (T - 1)
Agor
430
II j=t+1
1 I+ass a [K
By
+
Aat.
n
np
3+7
4
Under the choice 04
the last display gives
(((r++1)) Ax4)
2T (T +1)
Ad
C
(1+
8T <
+ p3Ca
II
n
tije
(T + +1) B Aal
s=t+1
(T( +1)
+ mp
Ag + MdCd
T
1
Σ
II
1+
(TK + 1) 3 +
Azh
1=1
j=t+1
2L2 + 3 3L
T C
T Σ
C
exp
n (ml
t
j
j=++1
212 + 3 + 3L
C
cT
nL3L.
t
exp
Clog
1+1
C (212 +B 3++ (L)
T
eT
n,
1+1
33

---

Published as a conference paper at ICLR 2024
(eTT) (2L² + 3 (L)
T
1
n,3L
80+1
(ET) C (2L2 3 3L)
min {C + 1, C' Colo (eT)}.
nL3L
Then the generalization error of ZO-GD with 1-point gradient estimation is bounded by
21.2 BL
(eT)) min(C + 1, Clog (eT)).
Cgen S
nB
Proof of Theorem 5 Recall that ut are independent for all ks K, tsT and the loss function is Lipschitz and smooth. The last display and the triangle inequality give
20, L
d1t1 Sno +
Σ
VV zi) - vf(w(, 2:ll
i= 1,igk
a4 rk / 23) v f( 2/y1 + asu3Caa
20 L (T +1)
S [1 + (r + 1) [] de
+ pBCaar
Then by solving the recursion we find
200 L (T +1) + pBCaor
8T
II j=++1
(1 ag (T + 1)
Under the choice at
S
the last display gives
((rz +1)8
2I.
87 <
r + u3Ca
II j=t+1
(1+ + Baj (1+1
+1 1 1 K
T
T
C8 ))
(2 c)
II j=
1+
n
(T +1
(2 L
C
Σ
CB
S (2+c) L
c
CBBlo
)
cT
exp
exp
j
n
j=H+1
C(2 e)
eT
C8
C(ET)
c)L
T
n
t++1
n
+C9+1
(2
CB +
C log(en)
min
B
Then the generalization enror of 70-GD with 2-point gradient estimation is bounded by
(2 L)
C3 + 3 , C Clog(ET) }
Egen <
min
n
Theorem 16 (convex), Assume that the loss f(,z) E [0.1] 1] is L-Lipschitz, convex and 3-smooth for all z Z. Consider the update rule Eq.equation
T4| with T the total number of iterates, 04 < C/ (rh + t) some (fixe) C > O and for all < T. Then the generalization error of ZO-GD with 2-point gradient estimation bounded by
(2+
(ET) CB min(
C3 +
..'log (cT)}.
gen
B
34

---

Published as a conference paper at ICLR 2024
Proof of Theorem 16 Recall that 7) 1, of are independent for all ks K, tsT and the loss function Lipschitz and smooth. The last display and the triangle inequality give
d+41 Snp + 20,
ar p
[V[(w,
VSWW)))))
==,,f,
r [ 2j)
Vf(w), 2f)1 + a,phCCa
n
20, (T +1)
<(1 1 B)6,
43Caas
n
Then by solving the recursion we find
T
20, L (T +1)
T
8T
+ pBCaas
II
(1 a
n
-=++
Under the choice at
the last display gives
1(r2
+1).8
87 1
2L r 1BC,
Ea. ar II (1+ + (a,
jut+1
pd K
+1 1
T
1+ CB
(2 + c)
II j=t+1
(I + 1)
j
2 e
C
Σ j=H+1
CB
(2 e
Ee exp
T Σ
CB
(+1) )+11)
eT
exp
n
j
n
C(2 C)
eT
C8
C(eT)
c)L
T
n
[+1
1C341
(2
CB +
C Clog(ee)) (T))
min
B
Then the generalization error of ZO-GD with 2-point gradient estimation is bounded by
(2 + e)
min (CB +1
.Clog( (ETT) (
Egen I
n
3
Theorem 17 (strongly convex), Assume that the loss [(,, E [0, is L-Lipschitz 7-strongly convex and B-smooth for all Z. Consider the update rule Eq.equation 14 with T the total number of
iterates, a < C/ (r + 1) 111ttfff for some (fixd) C > O and for all < T. Then the generalization error of ZO- with 2-point gradient estimation is bounded by
(2 + c)+
C3 +1 Cog (cT)).
Egen
(eT)
CB min
3
Proof of Theorem 16 Recall that v = 97 ot are independent for all ks K, tST and the loss function is Lipschitz and smooth. The last display and the triangle inequality give
84-"
8.41 End= +
20 + on "T
Σ i=1,i
IVf(we, vf(W(, +IIl
Q pk | 23)
Vf(ul, 2/)l app3Ca
anby )o, +
20 L (T + 1)
<
(1+ a
+ 133Carr
B+
35

---

Published as a conference paper at ICLR 2024
Then by solving the recursion find
T
20
(I
+1)
T II -=++1
(I+
+ uBCaac
8
B 3+7
Under the choice at
C
the last display gives
(( +1)8
2h
T
(1+ Ba,T a.87
8r 5
K + 133Ca
Σ
II
B+%)
11
j=t+1
21 pd K + 143Cd
T
Σ
II
(1+ Ba, + 1))
(1
Qt
j=++1
nd +1
T
C
1+ CB j
(2 + C)L
Σ
II j=t+1
n
(T
+1)
2 + L
T C
T
CB
(2 (2
T
C
cT
Σ
CB
exp
exp
t+
1=1
1=H+1
E=1
C(2 + c)L
ET
CB
C(eT)cs(2+)))
T
t++
10941
(2 min
CB +
C Clog(eT))
B
Then the generalization error of ZO-GD with 2-point gradient estimation is bounded by
(2T) L2
CB +
CClog(eT) }
gen
n min
3
6 Recall that t s T and the loss function is Lipschitz and smooth. The last display and the triangle inequality give
Proof of Theorem
8 nj; 20cL p300.
In this case we can use the l-expansivity of the update rule G. which uses the fact that the objective function is convex, Or < 2/3 and μ s. Hence, have
20, L + a,3c
E 18 1] < E [8x] +
Unraveling the recursion gives
2L + Be
E [6r]
an
Then the generalization error of ZO-GD with coordinate gradient estimation bounded by
2L + BeL
Egen
In this case we can use the -xppansiiy of the update rule G, which uses the fact that the objective function is y-strongly convex 04 1/8 and μ S s Hence, we have
20, L + 3,
E [5 S (1 a7) E [. +
n
36

---

Published as a conference paper at ICLR 2024
Unraveling the recursion gives
20l. a,3c
2T. + 3c
[8r]
S
(1--a7)
n
ny
Then the generalization error of ZO-GD with coordinate gradient estimation bounded by
2L + 3cL
Egen I
10
In this case objective function is Lipschitz, smooth and μ I eL Hence, have
the (1 + expansivia of the update rule G. which uses the fact that the
ng
E [5441 & (1 + B + 204 + a,3c
Then by solving the recursion we find
20 I
anBe
II a,8). j=t+1
n
n
Under the choice at S
C
the last display gives
(2+
L
(2 2)
C
8T
II
(1+ (1+ Baa) 5
II
1+
j=t+1
n
j=tt1
+ L
T
T
CB
(2 + e)L
T
cT
TT
exp
Σ j=tt1
<
exp
CBlog
(++1
t
j
n
C(2 + e)L.
T
eT
C8
C(ET) + C)L
T C)
[+1
1331
(2 min
CB +1
Clog(eT)
Then the generalization error of ZO-GD with coordinate gradient estimation is bounded by
(2
CB
C' ('logeeT)
Egen
min
7
3
I PROOF OF SVRG GENERALIZATION ANALYSIS
I.1 SVRG
Theorem 18 (Convex Case). Assume that the loss function f(;22 is 3-smooth, convex and L- Lipschitz for every Suppose that SVRG with step sizes Cis c/ms for m steps. Then, at stage S we have
Elos] < GeL + (23c +1) E(ōs-1].
(220
After S stages, SVRG satisfies uniform stability with
6L (
Ogen S
min fc+ 8-1, clog(es))
n
37

---

Published as a conference paper at ICLR 2024
Theorem 19 (Strongly Convex Case). Assume that the loss function f(;22 2) is y-smoothh.ystronnyy convex and L-Lipschitz for every 2. Suppose that we run SVRG with step sizes o4 I 1/B for m steps. Then, one stage have
6 + 1] (1 - o7) B(o.] 20,3(61] + 6L.zr
n
After S stages, SVRG satisfies uniform stability with
6SL
Egen
Theorem 20 (Nonconvex Case). Assume that the loss function f(; B-smooth, and L-Lipschitz for every z. Suppose that we run SVRG with step sizes 0₁ S C/ms for m steps. Then, at stage S we have
CB
(1+
2CB
6CL
CB
E S exp
E[6s-1] +
exp
s
n25
8
After K stages, SVRG satisfies uniform stability with
2
gon S
n3
At stage S, we have
[[88+1]
$ we
w/ - az (Vf 21) ff (wh, 2,)i + a [V (w1, Vf (w),,
1 n
1
+ a'
f (w1,2))
Vf (u1, 2i)
n
n
i=,,fj
i=1,7j
V (1)
v (w/s
n
2Lo an3B(r,] +
2Lo
+ 2oo
< r)1B[6
+ 3,
n
=5 + 20, [8 + 6T.g
Proof of Theorem 18
+ 6Laz
E[0:+1] [(] + 20, 3E[
67
6L
C
C
ax
23
a2 + 1
B[b S
28
Blod
71
n
m18
ms
n=l
6CL
2,8C
+
+ 1
B[8.].
118
For the S-stage, we have w. = wm and Ws-1 = W1. Then
6CL +
2,3C' +1) B(65-1].
[[65] S
ns
Summing the above inequality for S stages, and unraveling the recursion gives
6CL
Σ II (1+
s
23C
6L (ES) min {C+ (,
B[ös] <
j=++1
Note that E If (wr;2) - f (w/r 2) LE [6r]. then have
61 250 min {C 30' (,C,,CCle((S)))
Egen v
n
38

---

Published as a conference paper at ICLR 2024
Proof of Theorem
19
6La
E + S (1 - an) B[oo] + 2a/3(61] +
71
m- 1
6La m-1 1
= a1- [|b{] + 20
Σ
(1-a7)' E[61+ +
(1 - (1-
n
[=1
t=
6La
(1-(1-07)m)) +
2/ (1- (1-
+ (1 an)
B[61]
ary
6L
< B[ói] +
ny
For the S-stage, we have Wa = Wm and Wg-1 = =wi Then
67 ny
Eōös I Blóg
Summing the above inequality for S stages, and unraveling the recursion gives
6SL
Elós] S
Tey
Note that E If (WT:2) 2) f (w/r: LE [6r], then we have
6SL
Egen
Proof of Theorem 20
6Lor
[1 S + (4 [[].] + (61
+
n
CB
2CB
6CL
E[6,] +
B[6,]
STR
977
T25T
CB m
[B(6.]
2C8
Σ
CB
81
6LC
CB
8m
8m
8m
n8m
sm
CB [
2CB exp
CB
6CL
CB
< exp
+
B
+
exp
118
C3
203
E[b + 6C'
CB
cxp
1
exp
ns
s
For the S-stage, we have W. = Wmn and wi = W1. Then,
C 1 1+ 2C3
6CL
CB
E[8s] < exp
E El
exp
s
ns
s
Summing the above inequality for S stages, and unraveling the recursion gives
E[ös] < CB s
S
3C8
exp
j
j=8+1
3CC
5
Σ
(s + 1) 309
n
6LC
8 gl3CBB
n
3CB g30B
ng
39

---

Published as a conference paper at ICLR 2024
Note that E If (wy;2 2) f (w/;2)) LE [6y]. then have
29
Egen
n133
1.2 ZO-SVRG
Proof of Theorem
7 Recall that 17 + a,3, and then we have
E(óc+1] 1 1 + 3 a/B (Ia +) o.LAd
arLAd
Bldd + 2 a18 (T + +
Bl6
1
6L (I + 1) at
Ad
+
3133Car +
n
pm
C
20 +
6L2C + 3Bc + 33LC
1
+
[|6.]
B[ +
8m7
8m
n Lsm
1 1+
C
E[
2C m
Σ
1
C
81
Sm
sm
sm
t=
6L2C + 33C + 33LC
Σ
1 +
n&Lsm
C' 14
20
6L + 33 + 33L
C
< exp
B[8,] +
exp
nBLs
For the S-stage, we have W = Wm and Ws-1 = W1. Then,
C'
2C's
Elos 67 +33 33L
C
Blās| S exp
1+
exp 8
nBLs
Summing the above inequality for S stages, and unraveling the recursion gives
6L + 33 + 33L
Σ
5
3C
exp
n3L
j
j=8+1
(6L2 + +33 + +33L)
ec S3C
1
n3L
(s + 1) 30
(6L + 33 + 3BL) e gac
1
n,LL
8 g++30
(2L² + 3 BL) S3C
n3LC
Note that E If (WT;2) - f (w/iz)l s LE [6T], then we have
(2L + B + BL) S3C
Egon <
n3C
Theorem 21 (convex). Assume that the loss function f(;;2) is B-smooth, convex, and I-1 ipschiit for every Suppose that we run ZO-SVRG with step sizes ar < (sm((() + 1) + LAg for T steps. After S stages, 70-SVRG satisfies with Then, at stage we have [8(5s]
exp C8 1+ 28c E|os-1]+ + +32+38+38L
BLas exp C. After S stages. ZO-SVRG satisfies with Egen S
(2T.2 + S3C exp C/CBB).
40

---

Published as a conference paper at ICLR 2024
Proof of Theorem 27 Recall that 7) 1, and then we have
aoLAs
(1 + a,LAd
B|o++1] -
1 + a +
[[ + 2
1
69 (T + 1) an
Ad
+
+ 3333aan
pn
C
20
6T,2 + 3 + 33TC
B[o.]
+
B(
Sm
sm
Lsmm
C'
2C
6L + 33C + 33LC
C
1 +
+
1 +
81
+
1+
STT
n3Lmm
1=0
2C'
6L2 + 33 + 33L
C
$ exp
1 +
[6
+
exp
n3Ls
For the S-stage, we have wi = wm and wi-- = W1. Then,
C' 2C
67 + 032+33+- 3 33L
C exp 8
Blgs exp 8 1+
E g
nBLs
Summing the above incquality for S stages, and unraveling the recursion gives
6L + 33 + 3BL
3C
B|ós]
exp
n3L
j=s+1
(6L2 +33 33L) e g3c
8
nBL
(s + 1)a0
8=
(6L2 + +33 + 38L) e S30
1
nBL
s1+30
8=1
(2L2 + 3 - BL) e3c
n3LC
Note that E ff (WT32) f (whi 2) LIE [ÔT]. then have
(2L.2 + 3 + BL) e
Cgen
n3C
Theorem 22 (strongly convex). Assume that the loss function f(; is 3-smooth, "tstrongly convex, and L-Lipschitz for every 2. Suppose that we run ZO-SVRG with step sizes a4 S C/ (3 for
1)+ + LAi) [A4)) for T steps. After S stages, ZO-SVRG satisfies with Then, at stage we have E(ōs) S
p (
exp C8
I 29c Elds
612 +38+38L Blas
exp C. After stages, ZO-SVRG satisfies with
Egen 5 (212 + BB+BL)S3C Cx(
Proof of Theorem
0,97 22 Recall that 1) = 1- B4y
and then we have
Blo++1] S 1 + a a,3y
3+7 + aLLAs
[88.J] + 2 (a.31 + a,LAs
69 (T+ + 1) as + 3u33ac0
Aa
+
pan.
1 TT + + a.LAs
E[5.] + (og acLAs E(61)
41

---

Published as a conference paper at ICLR 2024
69
(T.
+ 1) at
Ad
+
+ 3a
pun
C
2C E
61,²C + 33c + +
+
B[o+]
+
ST
Lsm
C
m
2C m
6L'C 3,3 + 33LC m
C
1
+
1
61 +
1+
STR
Sm
Sm
n.Lsm
sm
1=0
2C
LL + 3, 33L
C
$ exp
1 +
[
+
exp
nBLs
8
For the S-stage, we have Ws = Wmn and wg- = wt. Then,
C 8 +
2C's Blos- +]+
6L +33 33L
C exp 8
Blós| S exp
n.3.s
Summing the above inequality for S stages, and unraveling the recursion gives
B[ös]
6L 33 + 38L
Σ
$
exp
3C
n,3L.
j
jms+1
(6L2 + +33 + 333) e g3c
1
nBLL.
(s + 1)aC
(6L +33 + 338)) ec g3c
1
nBL
s g1+3C
(2L2 + 3 + BB) S3C
n3L.C
Note that ff (w) - (w/: 2)1 S LE [6 then we have
(2L2 + B + BL) e 53c
Egen
n3C
Proof of Theurem g
6L (T& + +1) at
E S + 0r (T + 1)) B[5]] + 20,3 (T) + 1) E(6,]
+ +3a3Can
n
CB
B[6.] + 2CB
6CL 3cC
1
Blō,] +
8m
8Th
7.Sm
CB
2CB m
CB
6LC 3cC
m
CB
1 +
E[611 +
++
81 +
Σ
1+
sm
sm
sm
n.T
sm
1=0
1=
CB
2CB
6L
3c
C
exp
E +
cxp
8
n8
For the S-stage, we have w., = Wm and w. Wr. Then,
CB s
2C3
6L + 3c C3
Elgs] < exp
1+
E -]+ +
exp
n²
s
Summing the above inequality for S stages, and unraveling the recursion gives
Blös]
(6L + C8
Σ
5
1
exp
3C3
n1
j
j=8+1
42

---

Published as a conference paper at ICLR 2024
(6L + sc}e 3c)ec353ce 530s
8
1
n
(s + 1)
3GB
e=1
(6L + 3c)e C9 530s
8
1
s1+303
(2L + c) g308
nB
Note that B (wT;;) I (w/y; 2)] LE [6r] then have
(2L + CC
Egen
73
Theorem 23 (convex), Assume that the loss function f(; 2) is B-smooth, convex,and L-Lisschitz for every Suppose that we run ZO-SVRG with step sizes 04 S. C/sm s/sm// (T + 1) for T steps. After S stages, ZO-SVRG satisfies
Egen 1 (2L + cL)) exp C3/(
Proof of Theorem
23
Recall
1, then we have
6L (1 + 1) at + 3p3C2ar
E $ (1
[ + 20 30
n
C
2
6CL + 3cC
x 1 1
B[ó +
8m
877
718I7
CB)
m
2CB m
CB
6LC + 3cC
CB
1 1
Σ
1
81 +
Σ
1
sm)
Sm
sm
n.sm
sm
1=0
CB
2CB
67 +
3c
CB
S exp
+
E
exp
8
n1/3
For the S-stage, we have w, Wm and Wg- W1. Then,
Elōs] S exp CB (1+
2C3 s
6L + 3e
C3
R [[ 1] +
exp
n,
8
Summing the above inequality for S stages, and unraveling the recursion gives
(6L + C3
5
3CB
E[5s] <
Σ
exp
nB
j
j=st1
(6L + 3c)e
Ca C3C
S
1
1
n
8
(s 1) 303
(67. + 3c)e
C3 S3C8
g
8 s1+3CB
n
(2T. + c)e C3 $308
<
n2
Note that E lf 2) - f (wf:²2) 2)1 < LE [ör]. then we have
22L2 + cL) S3C3
Cgen v
n23
43

---

Published as a conference paper at ICLR 2024
Theorem 24 (strongly convex). Assume that the loss function f(:2) is B-smooth, convex,and L- Lipschitz for every z. Suppose that we run ZO-SVRG with step sizes Ot S C/sm (T²2 + 1) for T steps. After S stages, ZO-SVRG satisfies
Egen S (21? + cL)S exp C3/(
Proof of Theorem
24 Recall 17 -1
a.tt 34y"
then have
1 1+ 31 a,,7
6I. (T' + 1)arr 33pBCaar
E v
3+77 [06d]] 20, B1 +
n
6L (T2 + +1) 33
(1 B0
+ 1)) [66o] + 20x 3 +
n
CB
2C B +
6CL + 3CC
+ Sm
[B(6.]
Sm
1 1
C
[[61]
2CB m
1+
CB
81 +
6LC + 3cC
Σ
1+
CB
sm
ST
Sm
T&S
sm
1=U
1=0
CB
2CB
6L +
CB
$ exp
+
B +
exp
n,
8
For the S-stgge, we have W³, Wm and ws-1 = W1. Then,
2C3 Elós] S exp s 1+
CB
6L + 3c C3
E[ōs-1]+ +
exp
nz
8
Summing the above inequality for S stages, and unraveling the recursion gives
B(ōs]
(6T. + 3c)e 03
Σ
s
exp
3C3
nB
s
j
j=s+1
(6T. + 3c)e CD 53C3
S
1
(s + +)) 333
(6L + 3c)e
CB g309
s1+3CS
n
(2T. + c9 g3C8
n,
Note that Bl (wT; I (wfr =)] LE [ then have
(2L2 + CD
Egn 5
n23
Proof of Theorem 9 Nonconvex).
E 1 < (1 + 0, [[ + 20, + 6La;
31
CB
2033
6CL + 30C
1 +
E[8,]
E[81] +
sm
sm
nsm
CB
2CB m
C3
6TC + 3cC
CB
1
+
1
81 +
1+
STn)
STN
sm
715m
sm
1=0
C3
20B
6L +
3c
C3
exp
1
E E(51]
exp
8
n,3
$
44

---

Published as a conference paper at ICLR 2024
For the S-stage, we have w, Wm and Ws-1 W1. Then,
CB 8
20B
6L
+3c
CB 8
Blós] S exp
1 +
B B(ōs-1]
exp
n23
Summing the above inequality for S stages, and unraveling the recursion gives
(6L + 3c
S
3C3
Elós]
exp
nB
j j=8+1
(6L + Ca 530s
(s + )$CB
n
(6L + 3c)e c9 S309
81+309
n
(2I. + C g308
nB
Note that E f (WT;2)= - f (w/:: 2) S LE [ÔT], then we have
(2L² + Ca
Egen 1
n1
Proof of Theorem T Conver).
(6L + 3c)a:
B[8
<1] + 2a, [E
n
(6T + 3c)
04
23
O2
E[6r]
t=1
n=1
6L + 3e
m
C
m
C
2,3
+ 1
B[61]
n
ms
ms
n=1
6CL + 3cC
2,3
1 B[ōi].
ns
For the S-stage, we have w. = Wm and wS-1 W1. Then,
6cL + 3cC + 23c +1) Blos 1].
Eb8s <
Summing the above inequality for S stages, and unraveling the recursion gives
6CL + 3cC
1 1+ 28c
E
II
j=++1
(6L + 3c) (eS) 23c
min { + 1-..--1.coogl clog(es))
Note that E (WT;2) 2) - f (w/r 2) S LE [67]. then we have
(6I.2 + 3cT. (e5)22c
23c
Cgen <
min {ct + g-1 (clog((()))
45

---

Published as a conference paper at ICLR 2024
Proof of Theorem 9 Strongly Convex).
(6I. + 3c)a
Big + 1] - (1 - a7) B[ō.] + 20:3(51] +
(6L + 3c)a m-1
(1 07) [E[1i] 20.3 Σ
(1 - a-) [B(b)] +
Σ (1 (1-
n
t=
(6L + 3c)a
1 -1-1--001") (1- an) ) ?
2B
(1 a7) B[ó1]
n1
ary
69 + 3c
[[0]] +
ny
For the S-stage, we have Wg = wm and ug-1 = W1. Then,
6T. + 3c
Elos] [
107
Summing the above inequality for S stages, and unraveling the recursion gives
6LS + 3cS
E[ds]
nry
Note that [ (WT; 2) - f (w'; S LE [87], then we have
6SL 3cLS
gen S
ny
46


Reviews:
[{"review_id": "9M9VpLx9Sp", "reviewer": "Reviewer_PNwi", "summary": "In this submission, the authors proposed a general frame-work to prove the generalization error for the zero-order optimization methods. They proved the generalization error bounds for different zero-order optimization algorithms such as SG, GD and SVRG under different convexity conditions. They also conduct numerical experiments.", "questions": "Please check the weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This submission is very clear with simple structures and languages. The main idea is natural and understandable. The mathematical and theoretical analysis is strict and the empirical results are consistent with the theoretical analysis.", "weaknesses": "There is no significant weakness for this submission. \n\nOnly one question is that for the ZO-SGD, ZO-GD and ZO-SVRG with one-point and two-point gradient estimation, the authors only presented the results for the none-convex setting. Is there any theoretical results for the general convex and strongly convex settings? Like the results for the coordinate-wise gradient estimation. If the authors could add these theoretical results, it could make the theoretical contributions much more complete.", "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": "oomD7YOMY8", "reviewer": "Reviewer_qUEd", "summary": "This paper focuses on zeroth-order optimization algorithms. While previous stability analysis results were limited to the basic 2-point zeroth-order estimate with a Gaussian distribution in stochastic gradient descent (SGD) algorithms, this paper introduces a general proof framework for stability analysis. This framework is applicable to convex, strongly convex, and non-convex conditions and provides results for various zeroth-order optimization algorithms, including SGD, gradient descent (GD), and stochastic variance-reduced gradient (SVRG) methods. It also covers different zeroth-order estimates, such as 1-point and 2-point estimates with various distributions and coordinate estimates. The general analysis reveals that coordinate estimation can lead to improved generalization bounds for SGD, GD, and SVRG versions of zeroth-order optimization algorithms by reducing the expansion in stability analysis.", "questions": "Majors:\n\n1. What is the zeroth-order estimator used in the experiments?\n2. How do different zeroth-order estimators affect the optimization performance?\n\nMinors:\n- Please indicate beta and C in Table 1.\n- Figure 2(b):  Generalization error: GD - >  Generalization error: SGD?\n- More implementation details are needed.\n- Utilize parenthetical citations to enhance readability.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper exhibits a well-organized structure, including a clear motivation, an extensive literature review, and a rigorous theoretical analysis. However, I have not verified the validity of all statements in the Appendix.\n- One intriguing and original contribution of the paper is its theoretical assertion that coordinate estimation can enhance the generalization bounds for zeroth-order optimization algorithms like SGD, GD, and SVRG.", "weaknesses": "- Theoretical contributions, especially those stemming from the primary theoretical lemmas (Lemma 3 and 4), are incremental compared to prior works such as (Hardt et al., 2016) and (Nikolakakis et al., 2022).\n- The paper could benefit from more extensive numerical experiments and a more detailed implementation section. Specifically, it should include a comparison of the performance of various zeroth-order estimators, providing empirical support for the favorable theoretical results associated with coordinate estimation.\n\n(Hardt et al., 2016) Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225–1234. PMLR, 2016.\n\n(Nikolakakis et al., 2022) Konstantinos Nikolakakis, Farzin Haddadpour, Dionysis Kalogerias, and Amin Karbasi. Black-box generalization: Stability of zeroth-order learning.", "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": "LwnAe9YlkH", "reviewer": "Reviewer_x656", "summary": "In this paper, a new simple framework for analyzing the generalization error of zeroth order optimization for Lipschitz and smooth objective functions is proposed and several novel generalization bounds are provided. The framework proposed consists of a method for analyzing the stability of a given optimization algorithm, based on the notions of boundedness and expansivity of the corresponding update rule. The update rules considered all correspond to zeroth order analogues of first order optimization algorithms, where a first order oracle is approximately simulated using queries to the values of the objective function (i.e., a zeroth order oracle). The simulated oracles considered are based on either 1-point, 2-point or coordinate-wise approximation, and the latter achieves the tightest generalization bounds for each of the algorithms considered, matching, in each case, the best known bounds achievable by the corresponding first order algorithms in each of the cases where the objective is strongly convex, convex or non-convex. The algorithms considered are Gradient Descent, Stochastic Gradient Descent as well as Stochastic Variance Reduced Gradient method. The theoretical guarantees of the paper are accompanied by experimental results on real world data.", "questions": "Could your results be extended to the case where the objective function is not smooth? Are there any generalization bounds for this setting, even for first order algorithms?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The results provided in this paper, which are obtained by leveraging a simple yet powerful framework and the idea to approximate the gradient of a smooth and Lipschitz function coordinate-wise, are strong and, to the best of my knowledge, novel. The presentation of the results is clear and detailed.", "weaknesses": "One potential weakness of the paper is that the results assume that the objective function is smooth, which, in many important optimization problems (e.g., learning ReLU networks) is not true.", "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": "J0vZItzHur", "reviewer": "Reviewer_N2Y8", "summary": "This paper considers the generalization bound of zero-order methods and presents a general analysis framework. Results on 2-point, 1-point, and coordinate-wise gradient estimators are established, which improves the existing work in this direction. Based on these results, the authors show that coordinate estimation leads to tighter generalization bounds for many zeroth-order methods. Experiments are also provided to verify the theoretical conclusions.", "questions": "In Figure 1 (b), why did the generalization bound of ZO-SVRG decrease at the beginning?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-presented and well-organized. The motivation, technique, and results are clearly stated.\n\n2. The framework established is a nice theoretical contribution. Consequently, the generalization bounds of many zero-order methods are developed. Moreover, the differences between these generalization bounds are captured and analyzed, making the whole theory complete and convincing.\n\n3. The technique used in the paper is solid and interesting.", "weaknesses": "It would be better if the author emphasized the new technique and idea used in this paper compared with the existing work by Nikolakakis et al. (2022).", "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)