Fine-Grained Theoretical Analysis of Federated Zeroth-Order Optimization
Authors: Jun Chen
Hong Chen
Bin Gu
Hao Deng
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated zeroth-order optimization
stability analysis
theoretical guarantee
non-convex optimization
sub-Weibull distribution

Abstract: Federated zeroth-order optimization (FedZO) algorithm enjoys the advantages of both zeroth-order optimization and federated learning, and has shown exceptional performance on black-box attack and softmax regression tasks. However, there is no generalization analysis for FedZO, and its analysis on computing convergence rate is slower than the corresponding first-order optimization setting. This paper aims to establish systematic theoretical assessments of FedZO by developing the analysis technique of on-average model stability. We establish the first generalization error bound of FedZO under the Lipschitz continuity and smoothness conditions. Then, refined generalization and optimization bounds are provided by replacing bounded gradient with heavy-tailed gradient noise and utilizing the second-order Taylor expansion for gradient approximation. With the help of a new error decomposition strategy, our theoretical analysis is also extended to the asynchronous case. For FedZO, our fine-grained analysis fills the theoretical gap on the generalization guarantees and polishes the convergence characterization of the computing algorithm.

Fine-Grained Theoretical Analysis of Federated Zeroth-Order Optimization
Jun Chen', Hong Chen 1.2.5.6, Bin Gu Hao Deng
CCollege of Informatics, Huazhong Agricultural University, China
2 Engineering Research Center of Intelligent Technology for Agriculture, China
SSchool of Artificial Intelligence, Jilin University, China
*Mohamed bin Zayed University of Artificial Intelligence
Shenzhen Institute of Nutrition and Health, Huazhong Agricultural University, China
Shenzhen Branch, Guangdong Laboratory for Lingnan Modern Agriculture, Genome Analysis Laboratory of the Ministry of Agriculture, Agricultural Genomics Institute at Shenzhen, Chinese Academy of Agricultural Sciences, China c 88544872438163 com, chenh@mail hzau. edu cn, jsgubin@gmail com, dengh@mail. .zau edu, on
Abstract
Federated zeroth-order optimization (FedZO) algorithm enjoys the advantages both zeroth-order optimization and federated learning, and has shown exceptional performance on black-box attack and softmax regression tasks. However, there is little generalization analysis for FedZO, and its analysis computing convergence rate is slower than the corresponding first-order optimization setting. This paper aims establish systematic theoretical assessments of FedZO by developing the analysis technique of on-average model stability. We establish the first gener- alization error bound of FedZO under the Lipschitz continuity and smoothness conditions. Then, refined generalization and optimization bounds are provided by replacing bounded gradient with heavy-tailed gradient noise and utilizing the second-order Taylor expansion for gradient approximation. With the help of a new error decomposition strategy, our theoretical analysis is also extended the asynchronous case. For FedZO, our fine-graines analysis fills the theoretical gap on the generalization guarantees and polishes the convergence characterization the computing algorithm.
1 Introduction
Federated learning collaborates multiple local clients to train a global model without sharing local raw data, which often enjoys great ability in protecting data privacy [1]. The training steps of federated learning include local clients receiving the global model from the central server, the local models being updated by the global information and local data, and the updated local models being uploaded to renew the global model. Based on this building-block process, rich federated learning algorithms have been formulated match different motivations, where their properties on privacy protection (2 [ and convergence rate 6 [7] g are investigated. In general, the existing algorithms of federated learning depend heavily on the gradient information of loss function, see e.g., [ 7 g Indeed, there are some learning scenarios where the gradient or Hessian information
"Corresponding authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

is either unobtainable or too expensive to obtain, such as reinforcement learning 19 TO II, meta learning [12], black-box adversarial attacks [4] and hyperparameter tuning [15]. To alleviate the dependence on the gradient or Hessian information, a federated zeroth-order optimization (FedZO) algorithm is proposed in [16] by integrating zeroth-order optimization into federated learning. In theory, the analysis of optimization convergence of FedZO has been established in [T6], which shows the linear speedup in terms of the numbers of local iterations and clients participating in the update for the global iteration. However, there is little generalization analysis for federated zeroth-order optimization.
The goal of generalization analysis is to evaluate the capability of the empirical risk to approach the theoretical optimal risk on a given dataset. To characterize the generalization performance theoretically, there are four popular analysis techniques including uniform convergence approaches
17
18
19
20], operator approximation techniques [2]
22 information-theoreti tools [2] 24 25
26
27
and algorithmic stability analysis [28 29, 30 (31 Usually, stability- based generalization
assessment enjoys some benefits over other tools. Firstly, in contrast to uniform convergence
approaches, the theoretical guarantees derived from algorithmic stability analysis are independent of the capacity measurement of hypothesis function space [32]. Secondly, algorithmic stability analysis is available in a wide range of applications rather than only some models enjoying operator representation [33 34]. Finally, data distribution does not affect the results of algorithmic stability analysis, whereas
cetmmattoo-thhoreete tools are typically sensitive to data distribution [25] (3). To
the best of our knowledge, there is only one work on the stability-bar -ased generalization analysis for the zeroth-order optimization, i.c., zeroth-order stochastic search (ZoSS) method [36). Following this line, it is natural to further investigate the generalization guarantees of the FedZO algorithm. However, due to the essential difference between FedZO and ZoSS, the previous analysis technique in (36] can not be used for federated learning directly. In this paper, we develop the fine- fine-grained error decomposition and estimations to overcome the challenge induced by the federated algorithmic formulation.
As general assumption for loss function, Lipschitz continuity has been employed in many stability- based generalization assessments, see e.g., [3 37 38
39 40). However, the index of Lipschitz continuity is likely too large or even infinite for some learning problems, which makes the previous results invalid [2]. With the help of the on-average model stability tool, [32] established the fine- grained generalization analysis of stochastic gradient descent (SGD) by removing the Lipschitz continuity and the convexity of each loss function, and relaxing the smoothness to Holder continuity. Moreover, (38) additionally considered the bounded variance of the stochastic gradient get the generalization bounds of non-convex SGD with high probability. Inspired by (32) and (38), this paper considers the heavy-tailed gradient noise (Assumption ( as a refined version of bounded variance of gradient and adopts the second-order Taylor expansion for gradient approximation to remove bounded gradient condition. Conclusively, we fill the theoretical gap in the generalization analysis of the FedZO algorithm [6 and its asynchronous version. The main contributions of this paper are outlined as follows.
Generalization bounds of FedZO. We provide the first generalization bound of general FedZO after building the relationships between generalization error and & on-average model stability. To alleviate the restriction of bounded gradient, we further get a refined generalization bound and an optimal optimization bound under the condition of heavy-tailed gradient noise and the second-ordes Taylor expansion of gradient approximation.
Learning guarantees of asynchronous FedZO. For asynchronous FedZO, we design new error decomposition strategy to bridge the relationships between each local model parameter and the global model parameter in each iteration. Then, the generalization and optimization bounds are derived for the asynchronous case. In particular, our fine-grained error bounds are tight even compared with the previous results for SGD implemented by the first-order optimization
32
37
38 and zeroth-order optimization 36
2 Preliminaries
This section introduces some notations and definitions preparing for our theoretical analysis. Besides, we also give some detailed explanations for every symbol in Appendix A.

---

is chosen to update the model parameters of federated learning, where wi is the local model parameter by of the i-th client at the 1-th iteration, {=(_m] and { are two sets of independent and identically distributed (i.i.d.) random samples and i.i.d. random direction vectors (satisfying the Considering a veroth-order optimization algorithm for federated learning, we rely on N clients to independently train global model. In each iteration, a subset of M clients is randomly selected to use their local data to obtain the corresponding gradient information. Then, this information is transmitted to the central server to update the global model parameter. For any E [N]. let 2; be random variable obeying data distribution D; associated with the i-th client. Denote S == {S.) i=1 as the total dataset, where S, == {zi1, Fan is the i-th local dataset and each sample žij is drawn independently from the distribution D,, i E [N].
Federated learning aims to optimize model parameters with the collaboration among all local clients, i.e. minimizing the following population risk
N Σ P((ws) = F(w) = N
N Σ BELND, [fi(ws; 2+)]
1
where w, w, E We Rd denotes the training parameters for the global model and the i-th local model in d-dimensional hypothesis space respectively, F(w) and (w,)) indicate the population risks for the global model and the local model of the i-th client respectively, fo denotes the loss function the i-th local client, and Ez,-D, [.] denotes the conditional expectation with respect to (w.r.t)) the sample
2,. Generally, the unattainability of the local population risk (w:) forces us to train the model by minimizing the following empirical approximation of population risk F(w)
N
N
1 nN
Fs(w)= = N M Fs. (w,) =
f((w; 2ig),
(2)
where (s(w)) and Fs, (wx) indicate the empirical risks for the global model and the local model of the i-th client respectively. Note that, for the update of the global model, the contribution of each client is treated equally. This paper considers the learning scenarios where the gradients (or Hessian information) of local loss functions are either unobtainable or too expensive obtain [16). Naturally, the first-order gradient estimation fi. defined as, for any t, b2 N, E [b.]. b1 [m][[n]] := (l....,.)).
1 by
ofe (fr (wf + wuhee zi,m) fo (wf: 2f,,))
fi 10,::,,m. (of1)
1=
by P
d-dimensional uniform distribution), and represents the distance between two model parameters (wf + pof, and w used to estimate gradient in the 1-th direction. In our analysis. the following second-order Taylor expansion is employed approximate Vi..
fa (wf =
1 b2 Σ (VVii(uf) o
of + (5 T fi fumi 2
21y) -e 2i.) ei.))
Note that, the number be of random direction vectors is set to be greater than the hypothesis space dimension d in this paper, such as the requirement of (I3 = 2d).
The update process of FedZO is formulated as follows,
b
++ = w0-
n
Vfz (if: 24,m (1t1)
w = w.,
b
M
m=1
where n/ and M2 E [M](MM = M) denote the step size and the collection of selected client indices in the t-th iteration, respectively. In particular, also consider the asynchronous FedZO algorithm.
Let
wº arg min F(w) and w(S) E arg min Fs(w), wEW
(4)
wew
where F(w), (u) are defined in 4 and (2. Denote A(S) = wT as the output of the global model after T iterations with any federated learning algorithm A (including Algorithm i...
3

---

synchronous FedZO). Typically, the excess risk of A(S) is measured by ([F((A(S)) - F((w")) and can be decomposed as
BIF(A(S)) F("") B[F(A(S)) Fi(A(S)) (EATAASS))-FFAA))))1CCAAAAA)))
(5)
where IE [-] denotes the expectation w.r.t. all randomness. The first part of (5) (called generalization error) measures the expected gap between population risk and empirical risk, while the second part of (5) (called optimization error) measures the divergence between the trained model and the theoretically optimal model. In this paper, we simultaneously bound the generalization error and optimization error of FedZO.
The update strategy ( is associated with minibatch of i.idd samples. Due to the interaction among samples, it is hard to establish the stability-usedd generalization analysis of the minibatch case directly. Fortumately, an equivalent formula can tackle this difficulty by means of the properties of binomial distribution (see Appendix B.3).
Remark 1.
Remark 2. Compared with synchronous FedZO ([66) in Algorithm 7y. there are several essential differences for its asynchronous one described in Section 4 Firstly, we assume that all clients participate throughout the entire update process of the global model parameters. Secondly, once some client finishes gradient computation, this gradient will be transmitted to update the global model immediately without waiting for other clients. Then, the updated parameters of the global model will be back to the corresponding client, not the other ones. As a result, the local model of some client may inconsistent with other clients within the same iteration.
Algorithm Synchronous FedZO
Require: w
initial global model; nh: initial learning rate; b, by minibatch sizes for samples and direction vectors respectively; μ.: positive step size in the definition of the derivative; M: number of clients selected to update the global model in each iteration
for all ..., T - do Randomly select a clients set MM. let f)- ni/t for all E M, in parallel do Let w = w²
Generate {=f,m 1/1 m== and { (1
b2 from Dj and d-dimensional uniform distribution
{ 1=1
Compute Σhi Vi and upload it to global model
end for Update w' t (+1 by Eq.
end for
Ensure: Final global model w"
Inspired by Definition [32], we introduce a new definition & on-average model stability for federated learning.
Definition 1. The federated learning algorithm A is E on-average model e-stable if
A(S(5i)) A(Sbi))-((s))) A(S)]|
Se,
(6)
nN
where |-|| 1| is the Euclidean distance ||. 11. S {S:) sti) = { S (
S4t, ..... SN
S; = (zi s(5) {2a,,.., Zi 1)+ byg. 1). (2/s is drawn from D., Vi e
[N].j E [n]).
In Definition we assume that only one sample of one client is perturbed, other clients. Partieu- larly, as N = the current definition is consistent with the standard on-average model stability in
32 38 Compared with several other stability tools, the advantages of on-average model stability are listed as follows. First, on-average model stability is a weaker stability tool than uniform (model) stability. Second, on-average model stability measures the stability of model parameters w instead of function values fw) like on-average stability, which can improve analysis.

---

Definition 2. 44 For some 8, a. >> 0 and all x > 0, if random variable X satisfying
P( 2 x) S exp(-bxr)
we call sub-Weibull random variable (denoted as ~ subW where is a tail parameter.
Sub-Weibun Weibull distribution is heavier-tailed (longer-tailed) distribution than the sub-Gaussian (0 = 2 and sub- Tub-Exxonential (0 = distribution, which matches some real applications [42] and has been used for learning theory analysis recently [4]]44] 44]. This paper utilizes some sub- heb-Wil properties, derived from the moment generating function (MGF), to relax the bounded gradient assumption used
in [36 37 38 39 40)
3
Evaluating the Generalization of FedZO via Stability
This section establishes the relationships between the generalization error of FedZO and the on- average model stability in Theorem Detailed proofs are provided in Appendix B.2.
This paper makes the following assumptions for the loss function f& of i-th local client (i E (N). Assumption 1. (a) (L-Lipschitz continuity). For any wi, Wü W, [N] and some L 0, f satisfies V fe(wi z.) < L, that is
[f((wg 2.) f((w;; 2,)l S L 1|00 will 4zz D, (b) (B-Smoothness). For any wa, W; E W, é E [N] and some / > 0. fi satisfies [V V[((w,, =I S 3 ||0, - will, Vz, D,,
The requirement of Lipschitz continuity and smoothness is general in statistical learning theory, see e.g., 38 39 40). Usually, it appears to be justifiable when the hypothesis function space is uniformly bounded. However, the Lipschitz constant L may be infinite for some learning tasks with unbounded hy hypothesis function space (32). this paper, two attempts are proposed to remove the Lipschitz assumption. Firstly, we focus the zeroth-order optimization problem, where the gradient information unavailable. We approximate the first-order gradient using a second-order Taylor expansion to avoid the dependence the Lipschitz constant (see the proofs of Theorems 2 and 5). Secondly, we use weaker gradient-relate assumption, i.c., the heavy-tailes gradient noise assumption, to replace the Lipschitz assumption in our generalization analysis (see the proof of Theorem (b)).
1/2 the number of iterations t > and the client index E [N]. For any wi E W, S,,, S; E D., we assume that the gradient noise fi( 2f) - Fss, (w() is sub- weibull random vector, i.e., fi 24) - (F,(w)) ~
Assumption 2. (Heavy-tailed gradient noise). Let the tail parameter
subW (0).
From Theorem 2.1 in 41,, we deduce that the MGF of || fi(1f(;f] Fss (w)) ||
can be bounded
some point, i.e., E exp [IVA((ef=))--E
(
2 for some K 0. Moreover, random
K
variable X is defined K-sub-WeibullCy EE exp (
< 2 45 Therefore, the gradient
noise in Assumption can be also denoted as V fi z Fss, (wf) subW K). In this paper, a lemma (Lemma in Appendix B. /) related to the bounded p-th norm of the lub-Weibull variable is used to build novel relationship (Theorem (b)) between & on-average model stability and generalization error.
Assumption 3. (PL condition). For any W, UN D. and some the empirical risk Fs (w) satisfies
[Vs(w))] 2 2nE (Fs((w) Fs(w(S))))-
Assumption 3 ellucidates that the quadratic gradient of the empirical risk enjoys linearly decreasing
lower bound 46). Without the setting of convexity, the gradient of empirical risk [/V]l = just sufficient condition for a local optimal model instead of the guarantee to find global optimal
5

---

parameter. This assumption implies that all local optimal parameters are global optimal parameters, that is, [VF(())]| 0 implies that [w)) [[F(w(S))]
E[ ((F holds in expectation.
For this reason, we can study the optimization enror with the form (s(w)) - (s(w(S)) rather than ((ww)
44 under the non-convex condition.
Now we state two quantitative relationships between generalization error and & on-average model stability.
Theorem 1. Let S, be given in Definition and A be federated learning algorithm.
(a) Let Assumption 7 (a) hold and A be & on-average model c-stable. Then, for some O,
N
[[F(A(S) Fs(A(S)M &
- A(S) S Lc.
nN
(b) Let Assumption hold and be E on-uverage model e-stable. Then, for some
1 > 0,
[[F(A(S)) Fs(A(S)) (40)
ΣΣ E || - A(S) -(()) (R(F)(
nN
<(4) 0 Ke + 2E (s(((S)))
Theorem provides the generalization bounds of the FedZO algorithm by the E on-average model stability. Essentially, Theorem (a) is consistent with Theorem 2 (a) in (32 and Theorem (b) states a refined upper bound independent of the Lipschitz constant L. Explicitly, in Theorem I (b), the
tail parameter 0 in the first term is typically bounded [4] and the second term [PPs(A(S)] has no
significant negative impact on the upper bound 32
In the sequel, derive the generalization bounds by integrating Theorem and estimations of L on-average model stability. Mcanwhile, some optimization bounds for FedZO are also provided. Table T and Table 2 report the comparisons of our results with the related theoretical analysis for ZoSS 36), AD-SGD [47), AD-PSGD 48) EF-ZO-SGD, FED-ZO-SGD 49,, FedZO [6] and SGD
37
38
39
40
50
without the convexity requirement of loss function.
3.1
Generalization Analysis of General FedZO
This subsection considers the FedZO under the general setting.
Theorem 2. Les [w"} and {w²} be produced by FedZO (3) on S and S(d.) respectively, where
= -n(- 711 (2a1)-1 with parameters A(S) TH and A(S(5.)) = respectively. Under Assumption there holds
(1+ vd/b2) B. After T iterations, get the global
N
w0 -
-w w1 s (e (T - 1)) a2m log (e (T 11),
nN
=1
where d2 22n - u3 + 2(n2) Lddb22
d/b2.
Theorem states a & on-average model stability bound with order O ((nnN)-'L+ (1) T log T)
under mild conditions of parameter selection. When O ((nN)-+), the upper bound is equal to which is comparable with the existing stability bounds for ZoSS (36 and
O (nN) log T'
SGD
37
52 under similar choices of step sizes.
The following corollary is derived by integrating Theorem (a) and Theorem 2
Corollary 1. Under the same conditions of Theorem] 2 for FedZO 3 there holds
[[F((")) - Fs(w") || O (L ((nN)- + n) T logT).
When μ = O ((nN)-)). it provides the generalization bound (((N)- L T'g for the general FedZO algorithm. When Bc/ (8c 1) > $ for some positive constant c, Corrollary ]

---

Table 1: Comparisons of stabilitt- generalization bounds under the non-convex condition TThm.-Theorem; Cor--Croollar; c-a positive constant; t²-the upper bound of the variance of gradient; X-a parameter characterizing the properties of decentralized topology; 6-high probability; *-high probability bound; B.-bounded loss function; Uni-uniffrm stability; fi-L1 on-average model stability;
/-has such property; X-hasn't 't such property; 17z
(v 1)/b2 + 1): @(N, T, tt)
(1 + Vlg? T (nNN) Vlog + to).
Algorithm
Assumptions
Generalization bound
Tool
Result
L
22
B.
SGD (n S c/t)
de L PETT TETT
337 (Thm. 3.12)
o
Uni.
V
X
V
SGD (1) S (++2) (o)((+)))
L( (BBlv/)+oor
4
(38] (Thm. 3)
SGD (m) S c/t)
39 (Thm. 3.5)
1. 1 T
Uni
X
SGD (1) S 2a(1+1)7
21+1
T
Uni.
40) (Thm. 15)
ZoSS (n) S c/ (11%)
L L.PTT L.ETTTpeT1 p
o
Uni.
[36] (Thm. 5)
ZoSS (n) I c/t)
0 I.2T
Uni.
X
[36] (Cor. 6)
ZoSS (n) S c/(()g) b2))
0
L
min
{e + 1-11 1, log( log(eT))
Uni.
[36 (Thm. 8)
ZoSS (m S c/ ((TT))) b2))
n2
Uni.
V
X
[36] (Thm. 7)
AD-SGD (n) 11))
47 (Cor. 2)
O
n|l n(1-
- T 1
Am
)r M
Uni.
V
AD-SGD (1: = M
3(++1)
o nM nM-A 1,27)
Uni.
V
X
X
47 (Cor. 2)
FedZO (7), <
Ours (Cor.
(NN + (1) LT log T
4
V
x
x
FedZO (1)=
Ours (Cor.
(( T n.
1) (40))ITT'S LeT's log
X
V
X
X
FedZO (7)+
Ours (Cor.
o ((o) wi'h vlggT
X
V
X
X
aligns with the previous generalization bounds of SGD algorithms for pointwise learning (Theorem
3.12 in (37)) and pairwise learning (Theorem 3.5 in 39 and Theorem 15 in [40]). (36) provided the first generalization error analysis for the minibatch ZoSS algorithm with both unbounded and bounded non-convex loss functions. Specifically, they presented the generalization bound n- (2 (eT) min {c 8-1, ,clog(eT)} (C' is a positive constant) with the decreasing step size
N c/ (ITz)) where r (V(2a (3d 1)/b2 + +1). Under the constant step sizes 7p < log(1 3c)/ (T and tpe S c/ (TT,,) they also showed the generalization bound n -12 + C)eL? and (n²3)~ + C") (e -1). When Bc 2 1. our generalization bound can match their first result. Indeed, we also can get similar bounds as [36] for the special setting of constant step size. Detail comparisons are also provided in Table
3.2 Learning Guarantees of FedZO with Heavy tails
Inspired by 4 44. we further investigate the learning guarantees of FedZO with the smooth, heavy-tailed loss function and PL condition.
7

---

Table 2: Comparisons of optimization bounds under the non-convex condition (Thm--Thoreet Corolloroll;y: D-ZO-PD (Distributed ZO Primal-Dual); r, Comem constants; A-a parameter characterizing the properties of decentralized topology; o-the upper bound of the square of gradient; B.-bounded loss function; v-has such a property; x-hasn't 't such a property).
Algorithm Result
Assumptions
Optimization bound
Step size
0
B
B.
Ø
47) (Thm. 8)
AD-SGD
O ((r
+
Ca X
fo +
M
T)
1)t = 0
2+1
M
V
X
V
X
X
48 (Cor. 2)
AD-PSGD
0 (T-
T 0
b((V+11)
n
X
X
V
X
V
EF-ZO-SGD
49 (Thm. 1)
0 T 1d3 + +
O
2T
X
V
X
X
FED-EF
-ZO-SGD
o
T b + +T =
7 = o
dT
X
X
X
(Thm.. 2)
16 (Cor.
FedZO
o ((MT) - + dp²)
7) S
Mb
dl
X
X
X
V
FedZO
Ours (Thm.
0 ( + 12)
7 S +
X
X
FedZO
Ours (Thm.
o 2 2 + 112
n S m
X
V
X
X
Theorem 3. Let {w'} and {w²} be produced by FedZO 3 S and S(1i) respectively, where
"I = =m--,, S get the global parameters A(S) wT and A(Sti)) nt respectively. Under Assumptions 1 (b). a there holds
L-d/b2 with 033 = (1 + d/b2) B, and 0 2 1-d/bz 2 omn - After iterations, we
Aag
N
"T TT 1] S (e (T-1)) 1)) as(T - 11m log (e 1)),
nN
i=1 1=
where as (T - 1) = 2(nN))117(P) - + n3 + 2(nN)- V d/b2 and T(T - 1) =
O (n² T)
Theorem 3 states the stability bound O (((nN)-1 VlogT + +1) (nN)- log T) if taking
O ((nN) and (1-d//))) S 1. Compared with Theorem 2 the current result removes the 4ng
dependence on the Lipschitz parameter L while the dependence on μ is improved from the partial dependence L/(n.V + μ to the full dependence A/logT//(n/) + 1)μ.. The reason is that, motivated by (36), we decompose the gradient approximation into two parts, i.e., the difference between the unknown gradient and its expected estimator, the divergence between the expected and its empirical version. With the help of second-order Taylor expansion, the first part is bounded by Lemmas 4 and in Appendix B.I. Mcanwhile, the second part is bounded by the PL condition. The detailed proof is provided by Equation (8) in Appendix B.4
Combining Theorem (b) with Theorem 3 we derive the following generalization bound for the heavy-tailed FedZO.
Corollary 2. Under the same conditions of Theorem 3 for FedZO 3 there holds
[E[F(WF) - Fss("")] = = (aan))-V/oog
Log T + (40)) am log + (L(Fs(")))
When / = o ((nN)-1), a1 (1/b2)) das
< 1 and E [F = o ((mN)-1), Corollary ()(4)) (nNN)-'T log 7). With
2 shows the generalization bound o <((( ((nN))-Voog bounded variance of gradient and bounded loss function,
[88 stated the generalization bound

---

VlogT) for SGD with high probability. Here, we further developed the analysis technique associated with the bounded variance of gradient to the federated learning setting by the fine-graine ane-grained error analysis (see the proof of Theorem (b))
o ((E))
Theorem 4. Let {w*} be produced by FedZO
3
S, where nt m1t 111
1-d/bz with
4ng
43 (1 d//b2) B and 0 2 I-d/br am 1. Under Assumptions
(b). and there hold
EIFs(w") (00-=Fs((()) s <0 (T-2 +
and
(w=² F(w")]l
0o T- + 12 122 (InN)~+vlon T + +1) (400)"Tmn log T ++F[FF((")))
where wSS), w" are defined (4
The PL condition can guarantee the identification of global minimizers. Therefore, we regard F's(w") F's(w))] instead of VV' (""((w")) I||, as the measure of optimization error this paper. provided the optimal optimization bound O (1/(Ta²) with uniform stability tool for gradient-
dominated pairwise SGD. [6 characterized the convergence rate O (MT) - + dp² of the
FedZO algorithm with partial device participation. As shown in Table 2 Theorem 4 guarantees the optimal decay rate O (T-)) on the optimization error as μ O without the dependence of the dimension of hypothesis function space d and the random direction number 62. Note that, our optimization bounds rely on the quality of the initial model like many previous work (e.g. (16)..
4 Learning Guarantees of Asynchronous FedZO
Following the line of Section 3.2 we further study theoretical foundations for the asynchronous case of the FedZO algorithm. Considering the asynchrony among the local model parameters of different clients in the same iteration, we modify Equation 3 follows
N
b2
w
VJ
(ol) (
b, N
where t E [tu] denotes the delay of the i-th client in the t-th iteration, and to max { 1E[2] :E[N]
max t,
min (x} denotes the maximum delay for all clients in the whole update process of the global model. vE[N]
Note that, if for some i, the parameter w will be updated to w at the end of the 1-th
iteration. We state the differences between Equations 3 and (7) in Remark 2
Theorem 5. Given S and 8(5 in Definition
| let {w") and (w-} be produced by asynchronous
FedZO on and S(i-) respectively, where 7) -,tt .7) S 1-d/b2 with ag (1 d/b2) B and
1ag
N 1-d/b2 am 1. After T iterations, we get the global parameters A(S) T and
2, T respectively. Under Assumptions) (b). 2 and 3 there holds
A(Sth)) =
N
[[[ 1"T - wIIl S (T -1) 28m (as lon(ooo(eTT--- + 4a - 1)m?)
where a5 a5 - = 11 113+4(nN)) / - 1)/4/b2.. 06 -T (bb b2-1) +
2 + d//b// ((b)N)-2 (1+ --ي) + 210) VF(T and F - = O (12² log T). 21o) + (2
Asynchrony can cause discrepancies among the local models of various clients w i = 1,..., N and the global model w" in the i-th iteration. Therefore, the primary challenge of asynchronous learning theory is to establish the relationship between w w and ||w w6'l. To overcome this
bottleneck, we design a new decomposition |uo - :. < |/w| _w' -wwi w() || I|ww w'|l

---

and then use second-order Taylor expansion to give upper bound of the first term on the right-hand
side of the inequality. When μ O ((nN)-1) and B(1-d/bx) 2.2 Theorem 5 provide stability
2ng
bound ((11+ (nN))''voo) Vlog T) log T + Vlog Tto) (nN)
Corollary 3. Under the same conditions of Theorem 5 for asynchronous FedZO 7 there holds
[B(F(W")- Fs(w")]]
0o ((()++)
(mn))~ log T + Vlog (to) (e 2e + BB(F((")))
Combining
Theorem
1
(b) with Theorem
5
when μ = B[Fs(w")
3 yields the generalization bound o( ((1 (n.V)-1 logT VlogTtu) (n.) 'Tb) which appears to be the first generalization bound developed for asynchronous federated learning algorithms. It should be noted that, due to the more complex communication structure, using the condition to = (the synchronous case) can not recover the generalization bound in Corollary
O ((nN)-1). B(1 ((1-d/ba)
1
Corollary
20s
2
Theorem 6. Let {w'} be produced by FedZO on S, where T) = nit m S
1-d/b2 with
4ag
43 = (1+ d/b2) B and 0 2 1-d/b2 om - 1. Under Assumptions (b). 2 and there hold
Blfs(w") (=(((F)() S0 00(T (T-2 + 2
and
[FF(w")) - F(w")ll
<o T (T- 1² + ((1 (nN) log T + Vlog (40)))T2288)
pT F[Fs(w"))).
where (S), w are defined
Theorem also develops the first optimal optimization bound O (T'22 n²) for the asynchronous FedZO. Based on Equation (5, the excess risk bound O + ((1 +1+ (nN)) T log + to
(40) -TTb can directly derived by integrating Corollary and this optimization bound when μ = [F = O ((nN)-1))
Conclusion
This paper fills the gap of theoretical guarantees for both synchronous and asynchronous FedZO algo- rithms. We develop the first generalization bound for general FedZO after bridging the quantitative relationships between generalization етrог and & on-average model stability. Moreover, fine- grainnd learning theory analysis is established by means of the heavy-tailed condition and the second-ords order Taylor expansion, where the derived error bounds are satisfactory even compared with the previous results for traditional SGD
37
32 38
and recent ZoSS [36]
Acknowledgments
This work was supported part by the National Natural Science Foundation of China (Nos. 12071166 and 62376104), the Fundamental Research Funds for the Central Universities of China (No. 2662023LXPY005), and HZAU-AGIS Cooperation Fund (No. SZYJY2023010),
References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas Communication--fficiee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statisties (AISTATS), volume 54, pages 1273-1282, 2017. 2017.
10

---

[2] Lichao Sun and Lingjuan Lyu. Federated model distillation with noise-free differential privacy. In Proceedings gs of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI). pages 3563-1570, 2021.
[3] Lichao Sun, Jianwei Qian, and Xun Chen. LDP-FL: practical private aggregation in federated learning with local differential privacy. In Proceedings of the Thirlieth International Joint Conference on Artificial Intelligence (IJCAI), pages 1571-1578, 2021.
[4] Robin C. Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective, 2017.
[5] Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pages 5201-5212, 2021.
[6] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Feddane: A federated newton-type method. In 53rd Asilomar Conference on Signals, Systems, and Computers (ACSCC), pages 1227-1231, 2019.
[7] Xinwei Zhang, Mingyi Hong, Sairaj V. Dhople, Wotao Yin, and Yang Liu. Fedpd: federated learning framework with adaptivity non-iid data. IEEE Transactions on Signal Processing, 69:6055-6070, 2021.
[8] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. A novel framework for the analysis and design of heterogeneous federated learning. IEEE Transactions on Signal Processing, 69:5234-5249 2021.
[9] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning, 2017.
[10] Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. Structured evolution with cmpact architectures for scalable policy optimization. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 969-977, 2018
[11] Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies competitive for reinforcement learning. In Advances Neural Information Processing Systems (NeurIPS), pages 1805-1814, 2018.
[12] Marcin Andrychowicz, Misha Denil, Sergio Gomez Colmenarejo, Matthew W. Hoffman, David Pfau, Tom Schaul, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems (NIPS), pages 3981-3989, 2016.
[13] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15 -26.
2017.
[14] Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In Proceedings of the 35th International Conference Machine Learning (ICML), volume 80, pages 2137-2146, 10-15 Jul 2018.
[15] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In Advances in Neural Information Processing Systems (NIPS), pages 2960-2968, 2012.
[16] Wenzhi Fang, Ziyi Yu, Yuning Jiang, Yuanming Shi, Colin N. Jones, and Yong Zhou. Communication-effiiienn stochastic zeroth-order optimization for federated learning. IEEE Transactions on Signal Processing, 70:5058-5073 2022. 2022.
[17] V. N. Vapnik, Statistical learning theory. Encyclopedia the Sciences of Learning, 41(4):3185- 3185, 1998.
11

---

[18] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. In Conference on Computational Learning Theory (COLT), pages 724-240, 2001.
[19] Felipe Cucker and Ding Xuan Zhou. Learning theory: An approximation theory viewpoint. Cambridge University Press, 2007.
[20] Hong Chen, Xiaoqian Wang, Cheng Deng, and Heng Huang. Group sparse additive machine. In Advances in Neural Information Processing Systems (NeurIPS), pages 198 198-208,400 2017.
[21] Stephen Smale and Ding-Xuan Zhou. Learning theory estimates via integral operators and their approximations. Constructive Approximation, 26:153-172, 2007.
[22] Lorenzo Rosasco, Mikhail Belkin, and Emnesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11:905-9344 9344, 2010.
[23] Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage, 2015.
[24] Jiantao Jiao, Yanjun Han, and Tsachy Weissman. Dependence measures bounding the explo- ration bias for general measurements. In 2017 IEEE International Symposium Information Theory (ISIT), pages 1475-1479, 2017.
[25] Aolin Xu and Maxim Raginsky. Information-theorrt analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems (NIPS), pages 2524-2533, 2017.
[26] Amir R. Asadi, Emmanuel Abbe, and Sergio Verdú. Chaining mutual information and tightening generalization bounds. In Advances Neural Information Processing Systems (NeurIPS), pages 7245-7254, 2018
[27] Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli. Tightening mutual information based bounds on generalization error. In IEEE International Symposium on Information Theory (ISIT), pages 587-591, 2019.
[28] William Rogers and T. Wagner. A finite sample distribution-free performance bound for local discrimination rules. The Annals of Statistics, 6:506-514, 1978.
[29] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
[30] André Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6:55-79, 2005.
[31] Shai Shalev-Shwarte Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 1 11:2635-2670, 2010.
[32] Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning (ICML), volume 119, pages 5809-5819, 2020.
[33] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 44(4):1363 - 1399, 2016.
[34] Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger convergence rates for least-squares regression. Journal Machine Learning Research, 18:101:1- 101:51, 2017.
[35] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M. Roy. fhormation-thooreti generalization bounds for SGLD via data-pependent estimates. In Advances in Neural Information Processing Systems (NeurIPS), pages 11013-11023, 2019.
12

---

[36] Konstantinos Nikolakakis, Farzin Haddadpour, Dionysis Kalogerias, and Amin Karbasi. Black- box generalization: Stability of zeroth-order learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 31525-31541, 2022.
[37] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better:
Stability of stochas- tic gradient descent. In International Conference Machine Learning (ICML), volume 48, pages
2016.
[38] Yi Zhou, Yingbin Liang, and Huishuai Zhang. Understanding generalization error of SGD in nonconvex optimization. Machine Learning, 11 111(1):345317 2022.
[39] Wei Shen, Zhenhuan Yang, Yiming Ying, and Xiaoming Yuan. Stability and optimization error of stochastic gradient descent for pairwise learning, 2019.
[40] Yunwen Lei, Mingrui Liu, and Yiming Ying. Generalization guarantee of SGD for pairwise learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 21216- 21228, 2021.
[41] Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel. tions: Generalizing nab-Gaussian and sub-Exponential properties to heavier-tailed distributions. Stat, 91)==318:1-88 2020.
distribu-
[42] Arun Kumar Kuchibhotla and Abhishek Chakrabortty. Moving beyond sub-Gaussianity in high- dimensional statistics: Applications in covariance estimation and linear regression. Information and Inference: A Journal of the IMA, 1 11(4):139-11456 06 2022.
[43] Mariaa Vladimirova, Jakob Verbeek, Pablo Mesejo, and Julyan Arbel. Understanding priors in bayesian neural networks at the unit level. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Muchine Learning (ICML), 2019.
volume 97, pages
[44] Shaojie Li and Yong Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. In International Conference on Machine Learning (ICML), volume 162, pages 12931-12963, 2022.
[45] Liam Madden, Emiliano Dall' Anese, and Stephen Becker. High-probability convergence bounds for non-convex stochastic gradient descent, 2020.
[46] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak- bojasiiiio condition. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), volume 9851, pages 795-811, 2016.
[47] Xiaoge Deng, Tao Sun, Shengwei Li, and Dongsheng Li. Stability-based generalization analysis of the asynchronous decentralized SGD. In the Thirty-Eigtth AAAI Conference on Artificial Intelligence (AAAI), pages 7340-7348, 2023.
[48] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 3049-3058. 2018
[49] Ege C. Kaya, Mehmet Berk Sahin, and Abolfazl Hashemi. Communication-efficie zeroth- order distributed online optimization: Algorithm, theory, and applications. IEEE Access 11:61173-61191, 2023.
[50] Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with gradient- dominated objective functions. In International Conference on Learning Representations (ICLR), pages 1-23, 2021.
[51] Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 21236- 21246, 2020.
[52] Zhenhuan Yang, Yunwen Lei, Payu Wang, Tianbao Yang, and Yiming Ying. Simple stochastic and online gradient descent algorithms for pairwise learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 20160-20174 2021.
13


Reviews:
[{"review_id": "Z1kUZngyhq", "reviewer": "Reviewer_xnUD", "summary": "This paper provides theoretical guarantees for both synchronous and asynchronous FedZO algorithms. It first establishes a generalization error bound of FedZO under conventional assumptions. Then, the bounds are further improved by using the second-order Taylor expansion and heavy-tailed gradient noise. The theoretical results seem promising; however, some technical concerns remain unresolved.", "questions": "[Comparison of generalization bounds]\n\nThis paper has mentioned, \"Due to the essential difference between FedZO and ZoSS, the previous analysis technique in [36] cannot be used for federated learning directly.\" So, why are the generalization bounds comparable with ZoSS in Table 1? It seems more reasonable to compare them with distributed zero-order optimization.\n\n[Comparison of optimization bounds]\n\nA vital challenge of zero-order optimization is the dimension issue of model parameters, as shown in Table 1 in FedZO. In this paper, how does it remove the dimension $d$ from the optimization bound? Is this improvement applicable to arbitrary zero-order optimization?", "limitations": "No limitations are discussed in the main paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper focuses on providing theoretical guarantees for the newly proposed FedZO algorithms. The mathematical tools used in the analysis are relatively advanced in recent literature. In addition to analyzing the original FedZO algorithm, this paper also extends its analysis to include asynchronous FedZO.", "weaknesses": "This paper primarily focuses on providing further theoretical guarantees for a recently proposed algorithm, which addresses a minor problem. As a result, the contributions and impacts to the federated learning community are limited. Furthermore, some assumptions and results are not well-justified, as discussed below.\n\n[Related to federated learning]\n\nIn federated optimization literature, heterogeneous data distribution across clients is a significant challenge. In the original FedZO paper [16], Assumptions 3 and 4 were used to describe the impacts of such heterogeneity. However, this paper seems to have overlooked this necessary aspect in the analysis, which could significantly affect the proof of Theorem 2.\n\n[Experiment]\n\nThis paper introduces asynchronous FedZO and provides learning guarantees compared to FedZO. However, the original FedZO does not evaluate the asynchronous version. It is crucial to include experimental evaluations of both synchronous FedZO and asynchronous FedZO in this paper to support the proposed theories.\n\n[Organization]\n\nOne key aspect of this paper is the approximation of the first-order gradient using a second-order Taylor expansion and Assumption 2. However, the details of these methods are missing in the main paper, making it challenging to follow the arguments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** ... overlooked Assumptions 3 and 4 of [1] ...\n\n**A1:** Thanks for your constructive comments. In the original FedZO [1], the reason for making Assumptions 3 and 4 is to connect the gradient of local empirical loss and the gradient of global population risk. The gradient of population risk characterizes the convergence of the FedZO algorithm which is one of the major theoretical contributions of [1].\n\nCompared with [1], we have the following two reasons why we didn’t make such assumptions.\n\n(1)Theorem 2: We can directly bound the gradient of local empirical loss with the Lipschitz parameter $L$ (see line 42 in Appendix). \n\n(2)Theorems 3, 4, 5, 6: We consider the gradients of all clients simultaneously (see Equations (8) and (13) in lines 60 and 90 of Appendix) rather than the one of single client like Assumption 4 in [1]. After careful checking, we find some mistakes in (8) and (13) (e.g., the decomposition strategy of norm). Luckily, they don’t make a difference in the order of our results. We have corrected them in our new manuscript.\n\nFollowing your comment, we will try to improve our results by further considering the impact of such heterogeneity.\n\n[1]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n***\n**Q2:** ... experimental evaluations...\n\n**A2:** Thanks. Some relevant experiments on FedZO had been provided in [2]. For the asynchronous version, many related work validates that the asynchronous strategy can take full advantage of the clients computation capabilities [3][4]. \n\nFilling the gap of theoretical generalization analysis is crucial for the development of federated zeroth-order algorithm, which is the major contribution in this paper. Our results conform to these empirical behaviors from both generalization and optimization perspectives which are listed as follows. \n\n**Generalization:** Our generalization bounds (Theorems 2, 3) are negatively correlated with the number M of selected clients at each iteration (the dependence $\\frac{1}{M}$ can be seen in lines 41 and 56 in Appendix). It is consistent with Figures 1(b) and 4 of [2].\n\n**Optimization:** Our optimization bounds (Theorems 4 and 6) are negatively correlated with the total iteration number $T$, which is presented in all figures of [2].\n\nTo further give empirical observation of the asynchronous version, some necessary experiments (similar to the ones of synchronous FedZO [2]) will be conducted later. We have utilized “global response” to provide Figure 1 to show the structure of asynchronous FedZO. \n\n[2]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[3]X. Lian, et al. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.\n\n[4]X. Lian, Y. Huang, Y. Li, and J. Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. NIPS, 2015.\n***\n**Q3:** ... Taylor expansion and Assumption 2 are missing in the main paper ...\n\n**A3:** Thanks. As shown in line 36 of Appendix, the unknown gradient is estimated by the second-order Taylor expansion. Following your valuable comment, we have supplemented the detailed steps of Taylor expansion in line 100 of the main paper. As for Assumption 2, we utilize some properties of sub-Weibull distribution to bound the gradient noise after estimating the gradient. We have also added a related remark following Assumption 2 to improve the readability of our paper. Considering the reader who is not familiar with this distribution, we have provided some sub-Weibull survival curves with varying tail parameters $\\theta$ inspired by [5], via “global response” (Figure 2).\n\n[5]M. Vladimirova, et al. Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions. Stat, 2020.\n***\n**Q4:** ...why comparable with ZoSS rather than distributed zero-order optimization?\n\n**A4:** Table 1 shows the comparisons of stability-based generalization bounds. The reason to compare with ZoSS is that it is the only one using stability tools to analyze the theoretical generalization performance for zeroth-order optimization algorithm. Indeed, as you mentioned, it is reasonable to make comparisons with distributed zero-order algorithms. Thus, we have added some comparisons about optimization bound, e.g., [6][7], in Table 2. Limited by the length of Rebuttal, parts of these new comparisons are provided in Table 3 of “global response”.\n\n[6]E. Kaya, et al. Communication-efficient zeroth-order distributed online optimization: Algorithm, theory, and applications. Access, 2023.\n\n[7]X. Yi, et al. Zerothorder algorithms for stochastic distributed nonconvex optimization. Automatica, 2022.\n***\n**Q5:** ... how remove $d$ from the optimization bound? Is this improvement applicable to arbitrary zero-order optimization?\n\n**A5:** For the optimization bound, the common technology is dimension related tool (e.g., uniform convergence) which is the major reason why removing the dimension $d$ is challenging. Different from this technology, the key of our proof is to directly build the iteration sequence $t(t-c)\\mathcal{E}[F_S(w^{t+1})-F_S(w(S))]$ (c denotes a constant) via the smoothness assumption, the PL condition and the step size setting $\\eta_t=\\eta_1/(\\alpha(t+a))$. After iterative computation, we can obtain the optimization bound $\\mathcal{E}[F_S(w^T)-F_S(w(S))]$. Our proof can’t be applied to the zeroth-order algorithm which is without these settings. Note that, our optimization bounds rely on the quality of initial model like many previous work (e.g., [8][9]). We have added a remark behind Theorem 4 to make the above statement.\n\n[8]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[9]H. Yu, et al. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. AAAI, 2019."}, {"review_id": "bUm0taQQcW", "reviewer": "Reviewer_QoKb", "summary": "This paper studies the generalization and optimization analysis of the Federated zeroth-order optimization (FedZO) algorithm. It develops tailored techniques for the federated setting to establish generalization bounds. One bound relies on Lipschitz continuity, and the second removes this dependency. The optimization error in the order of $\\mathcal{O}(1/T)$ is also developed for FedZO. The authors extend results to the asynchronous federated setting, where all the workers participate throughout the update process and asynchrony may cause inconsistency in local workers within the same iteration.", "questions": "Unlike other existing papers, all the findings in this paper rely on the $\\theta$ tail parameter of the Sub-Weibull distribution. The extent of this dependence's impact is uncertain in practical settings, and it would be helpful if the authors could provide insights or comments on this matter.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-crafted, and the authors effectively elucidate the distinctions from prior methods.\n\nThe theoretical results are quite comprehensive. Existing techniques in the literature may not be directly applicable to the FedZO algorithm. The authors fill in this gap by first developing error decomposition and estimation techniques and then presenting the first algorithmic stability-based generalization analysis for FedZO.  \n", "weaknesses": "The paper demonstrates a thorough analysis of the existing federated learning algorithm, FedZO, which is commendable. However, to further enhance its novelty and impact, it would have been valuable if the authors had introduced a new algorithm and conducted a comparative analysis against FedZO.\n\nFurthermore, to gain deeper insights into the analysis, it is recommended to include empirical evaluations exploring the effects of different parameters on the bounds. This empirical investigation would provide valuable practical implications and strengthen the overall findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** ... introduced a new algorithm and conducted a comparative analysis against FedZO.\n\n**A1:** Thanks for your constructive comments. Our major contribution is exploring the theoretical generalization upper bounds of federated zeroth-order optimization algorithm which seem to be a gap, especially for stability-based analysis. Not limited to FedZO [1], we extend FedZO to the asynchronous version and give a similar theoretical generalization bound. From the theoretical perspective, the bounds of asynchronous FedZO can recover the bounds of FedZO, which indicates this extension is theoretically reasonable. From the practical perspective, there are many related work [2][3] validating that the asynchronous strategy can take full advantage of the clients computation capabilities. To further explicitly show its effectiveness, some necessary experiments (similar to the ones of synchronous FedZO [1]) will be conducted later. We have used “global response” to provide Figure 1 to show the structure of asynchronous FedZO.\n\n[1]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[2]C. Xu, et al. Asynchronous federated learning on heterogeneous devices: A survey. arXiv, 2021.\n\n[3]A. Koloskova, et al. Decentralized stochastic optimization and gossip algorithms with compressed communication. ICML, 2019.\n***\n**Q2:** ... it is recommended to include empirical evaluations exploring the effects of different parameters on the bounds ...\n\n**A2:** Thanks. Our theoretical results are consistent with the relevant experiments in [4]. For example, our generalization bounds indeed have negative dependence on the number M of selected clients at each iteration (see lines 41, 56 in Appendix) which is presented in Figures 1(b) and 4 of [4]. Our optimization bounds (Theorems 4 and 6) are also negatively dependent on the total iteration number $T$, which is presented in all figures of [4]. As mentioned in A1, we will provide more empirical evaluations. \n\n[4]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n***\n**Q3:** ... The extent of the impact of the dependence on $\\theta$ is uncertain in practical settings ...\n\n**A3:** Some previous work indicated that the distribution of gradient noise of SGD exhibits heavier tail than sub-Gaussian (e.g., sub-Weibull [5][6][7]). In our paper, the distribution of gradient noise of each local client is equivalent to the one of SGD with the same model. Thus it is reasonable to assume that the real first order gradient noise for each local client is a sub-Weibull random vector (Assumption 2). It should be noted that the purpose of considering the heavy-tail condition is to provide the theoretical impact of heavy-tailed phenomena on the generalization performance of the FedZO algorithm. As your mentioned, due to the unknown gradient information, the dependence on the heavy-tail parameters $\\theta$ and $K$ is uncertain for practice yet. Luckily, our generalization bounds indicate that, in the federated zeroth-order optimization, the degeneration of generalization performance caused by the heavy-tailed phenomena is mild, which is similar to some previous theoretical results (e.g., Theorems 3.3, 3.9 in [5]). We have provided some sub-Weibull survival curves with varying tail parameters $\\theta$, which inspired by [8], via “global response” (Figure 2).\n\n[5]S. Li, Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. ICML, 2022.\n\n[6]L. Madden, et al. High\u0002probability convergence bounds for non-convex stochastic gradient descent. arXiv, 2020.\n\n[7] M. Gurbuzbalaban, et al. The heavy-tail phenomenon in sgd. ICML, 2021.\n\n[8]M. Vladimirova, et al. Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions. Stat, 2020."}, {"review_id": "axoBzunQs7", "reviewer": "Reviewer_hpvH", "summary": "This paper fills the gap of theoretical guarantee for the Federated zeroth-order optimization (FedZO) algorithm. It provides the initial generalization error bound for FedZO and presents refined generalization and optimization bounds. The structure of the paper is logical and the accompanying theoretical proofs in the supplementary material are comprehensive and robust.", "questions": "See above", "limitations": "Authors did not provide the limitation section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The need for filling the theoretical gap is important.\n2. The Author's contribution is solid.\n3. This paper is well-organized and easy to follow.\n", "weaknesses": "\nThis paper addresses a topic that isn't directly within my area of expertise, so my comments may not fully capture the nuances specific to this field, but I hope my remarks will prove useful to the authors.\n\n**1.** In Assumption 3, the authors refer to the PL condition but they do not explain what PL stands for earlier in the text.\n\n**2.** Regarding the assumptions made throughout the paper, it would be helpful if the authors could elaborate on whether each assumption is considered strong, mild, or weak, or if it is a relaxed version of a concept from previous work.\n\n**3.** The term \"heavy-tailed\" is used but not clearly defined. It would benefit readers if the authors could briefly describe what they mean by \"heavy-tailed\" early in the paper. In the context of imbalanced regression problems, is \"heavy-tailed\" equivalent to \"long-tailed\"? In my understanding, both terms refer to highly biased or imbalanced data.\n\n**4.** There are minor grammatical errors that need to be corrected.\n\nIn conclusion, this paper is well grounded and presents detailed, solid findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** ... not explain what PL stands for ...\n\n**A1:** Thanks for your constructive comments. As we all know, under the non-convex condition, local optimal model isn’t equivalent to global optimal model. Assumption 3 simply requires that the gradient grows faster than a quadratic function as we move away from the optimal function value [1], which stands for the fact that every stationary point ($|\\nabla F_S(w)|=0$) is a global minimum [2]. With this assumption, we can study the optimization error with the form $F_S(w)-F_S(w(S))$ rather than $|\\nabla F_S(w)|$ [3] under the non-convex condition. We have added a remark to clarify the meaning of PL condition following Assumption 3.\n\n[1]H. Karimi, et al. Linear convergence of gradient and proximal\u0002gradient methods under the polyak-łojasiewicz condition. ECML, 2016.\n\n[2]L. Lei, et al. Non-convex finite-sum optimization via scsg methods. NeurIPS, 2017.\n\n[3]S. Li, Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. ICML, 2022.\n***\n**Q2:** ... it would be helpful if the authors could elaborate on whether each assumption is considered strong, mild, or weak, or if it is a relaxed version of a concept from previous work.\n\n**A2:** The strength of assumptions is crucial for learning theoretical analysis. The related illustrations for all assumptions are listed as follows.\n\n(1)**Lipschitz continuity (bounded gradient):** It is one of the most general assumptions which is considered strong. Some milder related condition are provided in some previous work, e.g., Assumption 2.8 in [4]. We just assume the Lipschitz condition in our first case. In the rest cases, we introduce a milder assumption, i.e., bounded gradient noise (i.e., heavy-tailed gradient noise) to avoid the dependence on $L$.\n\n(2)**Smoothness:** It can be called bounded second-order gradient assumption which is also considered strong. Generally, Holder continuity is a milder condition than smoothness [5].\n\n(3)**Heavy-tailed gradient noise:** As mentioned in (1), heavy-tailed gradient noise can be regarded as a milder condition than Lipschitz continuity. It stands for a refined bounded variance of gradient which is similar to [6].\n\n(4)**PL condition:** It is commonly assumed in non-convex optimization [1][2][3]. [1] shows that PL condition is weaker than the main conditions that have been explored to show linear convergence rates without strong convexity, e.g., essential strong convexity[7][8].\nWe have added the above four illustrations following the corresponding assumptions respectively. In the last part of Appendix, we have discussed whether we can relax our current assumptions, e.g., whether we can relax smoothness to Holder continuity.\n\n[4]S. Li, Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. ICML, 2022.\n\n[5]Y. Lei, Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. ICML, 2020.\n\n[6]Y. Zhou, et al. Understanding generalization error of SGD in nonconvex optimization. Machine Learning, 2022.\n\n[7]J. Liu, et al. An asynchronous parallel stochastic coordinate descent algorithm, ICML, 2014.\n\n[8]I. Necoara, et al. Linear convergence of first order methods for non-strongly convex optimization. Math Program, 2019.\n***\n**Q3:** ... It would benefit readers if the authors could briefly describe what they mean by \"heavy-tailed\" early in the paper. ...\n\n**A3:** Your understanding of \"heavy-tailed\" is correct. \"Heavy-tailed\" is equivalent to \"long-tailed\". In this paper, we use a special heavy-tailed distribution, i.e., sub-Weibull distribution. We have briefly described the meaning of this distribution following Definition 2.\n***\n**Q4:** There are minor grammatical errors that need to be corrected.\n\n**A4:** Thanks. We have carefully checked the whole manuscript and correct all grammatical errors. For example, we have corrected Equation (5) to “$\\mathbb{E}[F(A(S))-F(w^*)]\\leq\\mathbb{E}[F(A(S))-F_S(A(S))]+\\mathbb{E}[F_S(A(S))-F_S(w(S))]$”."}, {"review_id": "3Lszi9Hi2E", "reviewer": "Reviewer_E5dV", "summary": "This paper studies the theoretical analysis for federated zeroth-order optimization (FedZO). The main contributions of this paper include 1) deriving the generalization bound of synchronous FedZO with different assumptions (bound gradient, heavy tail gradient noise). The main technical is to establish the relationship between generalization error and $\\ell_1$ on-average model stability; 2) deriving the generalization and optimization bounds for asynchronous FedZO. ", "questions": "1. It seems that (5) does not equal to $\\mathbb{E}[F(A(S)) - F(\\omega^*)]$. Could you please clarify?\n\n2. In the paragraph below (4), do you mean Algorithm 1 instead of Algorithm A?\n\n3. In Assumption 2, does $z_i^t$ means a data sample?\n\n4. In Theorems 2, 3 and so on, what is the physical meaning of $\\mu$?", "limitations": "There are no much discussion on the limitation of this paper.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper derives the generalization bound of synchronous FedZO with different assumptions (bound gradient, heavy tail gradient noise). The main technical is to establish the relationship between generalization error and $\\ell_1$ on-average model stability; \n\n2. This paper derives the generalization and optimization bounds for asynchronous FedZO with novel technique by a new error decomposition strategy.\n\n3. The paper is very well written. In particular, it explains the main technical challenges, main techniques and the implication of the results very well. ", "weaknesses": "I didn't find major weaknesses in this paper. Perhaps, it will be beneficial if the authors could provide some experimental study to validate the theories. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** Perhaps, it will be beneficial if the authors could provide some experimental study to validate the theories.\n\n**A1:** Thanks for your constructive comments. Considering the gap in the generalization analysis of federated zeroth-order optimization algorithm, the major contribution of this paper is providing its stability-based theoretical guarantee, which is meaningful to the development of this algorithm. At present, there are some works providing some relevant experiments on FedZO [1]. For the asynchronous version, many related work [2][3] validates that the asynchronous strategy can take full advantage of the clients computation capabilities. Our theoretical results conform to these empirical behaviors [1][2][3] from both generalization and optimization perspectives which are listed as follows.\n\n**Generalization:** Our generalization bounds (Theorems 2, 3) are negatively correlated with the number M of selected clients at each iteration (the dependence $\\frac{1}{M}$ can be seen in lines 41 and 56 in Appendix). It is consistent with Figures 1(b) and 4 of [1].\n\n**Optimization:** Our optimization bounds (Theorems 4 and 6) are negatively correlated with the total iteration number $T$, which is presented in all figures of [1].\n\nTo further explicitly show the efficiency of the asynchronous version, some necessary experiments (similar to the ones of synchronous FedZO [1]) will be conducted later. We have utilized “global response” to provide Figure 1 to show the structure of asynchronous FedZO.\n\n[1]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[2]X. Lian, et al. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.\n\n[3]X. Lian, Y. Huang, Y. Li, and J. Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. NIPS, 2015.\n***\n**Q2:** It seems that (5) does not equal to $\\mathbb{E}[F(A(S)) - F(\\omega^*)]$.\n\n**A2:** The complete form of Equation (5) should be $\\mathbb{E}[F(A(S)) - F(w^*)] \\leq \\mathbb{E}[F(A(S))-F_S(A(S))]+\\mathbb{E}[F_S(A(S))-F_S(w(S))]$ since $\\mathbb{E}[F_S(w(S))-F(w^*)]=F(w(S))-F(w^*)\\leq 0$. To avoid ambiguity, we have corrected it with the complete inequality. \n***\n**Q3:** ... do you mean Algorithm 1 instead of Algorithm A?\n\n**A3:** Algorithm A indicates the general federated learning algorithm including Algorithm 1 (synchronous FedZO). Theorem 1 is developed for Algorithm A, while the rest results (Theorems 2-6) are developed for Algorithm 1 and its asynchronous version (synchronous FedZO and asynchronous FedZO). We have made the above explanation in line 111 of the main paper.\n***\n**Q4:** In Assumption 2, does $z_i^t$ means a data sample?\n\n**A4:** Your understanding is correct. $z_i^t$ means the sample of the i-th client used at the t-th iteration.\n***\n**Q5:** ... what is the physical meaning of $\\mu$? \n\n**A5:** The meaning of $\\mu$ had been briefly explained before Equation (3). According to the definition of gradient, $\\mu$ represents the distance between two parameters used to estimate gradient. We have modified our related explanation to improve the readability of our paper."}, {"review_id": "DA9VuBFj0B", "reviewer": "Reviewer_oYUF", "summary": "This paper presents a detailed analysis of Federated Zeroth-Order Optimization (FedZO) by developing the analysis technique of on-average model stability. The authors establish generalization error bounds for FedZO and refine them using heavy-tailed gradient noise and second-order Taylor expansion. They extend the analysis to the asynchronous case and contribute to systematic assessments, on-average model stability technique, and improved bounds for practical FedZO applications. In short, the main contributions of the paper are the establishment of systematic theoretical assessments of FedZO, the development of the analysis technique of on-average model stability, and the refinement of generalization and optimization bounds for practical applications of FedZO.\n", "questions": "1. Can the authors provide more intuition behind the on-average model stability analysis technique? It may be helpful for readers who are not familiar with this concept to have a more intuitive understanding of how it relates to the generalization error.\n2. The authors mention that their refined generalization and optimization bounds have important implications for practical applications of FedZO. Can they provide some examples of these practical applications and how their results could be used in these scenarios?\n3. The paper focuses on the theoretical analysis of FedZO. Can the authors provide some insights into how their results could be used in practical applications of federated learning? For example, how could their results be used to improve the performance of real-world federated learning systems?", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. To my best knowledge, the authors provide the first generalization error bound of FedZO under the Lipschitz continuity and smoothness conditions, and also refine generalization and optimization bounds by replacing bounded gradient with heavy-tailed gradient noise and utilizing the second-order Taylor expansion for gradient approximation.\n2. This paper has also provided the theoretical analysis for asynchronous FedZO, which has in fact seldomly considered in the federated zeroth-order optimization field.\n3. The theoretical results are generally sound and can be inspiring for the follow-up works on federated zeroth order optimization.\n", "weaknesses": "1. While the authors provide a new error decomposition strategy for the asynchronous case, they do not compare their results with existing error bounds for other asynchronous optimization algorithms. \n2. This paper does not provide any experimental results to validate the theoretical findings, which may limit its practical relevance. Empirical verification may make this paper more sound. So, I encourage the authors to provide certain empirical experiments to validate their main theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** ... compare with other asynchronous optimization algorithms.\n\n**A1:** Thanks. Following your constructive comments, we have added comparisons with existing error bounds of asynchronous optimization algorithms [1] and [1][2] in Tables 1 and 2, respectively. Limited by the length of Rebuttal, parts of these new comparisons are listed below and in Tables 1, 2 of “global response”.\n\n**Table 1**\n\n| | | | | | | |\n|:----:|:----:|:----:|:----:|:----:|:----:|:----:|\n|**Algorithm+Reference**|**Generalization bound**|**Tool**|**L**|**$\\theta$**|**$v^2$**|**B.**|\n|**AD-SGD**[1]|$\\mathcal{O}(\\frac{n-\\lambda}{n(1-\\lambda)}(1+\\frac{\\beta \\eta_1 }{M})^T)$|Uni.|$\\surd$|$\\times$|$\\times$|$\\times$|\n|**AD-SGD**[1]|$\\mathcal{O}(\\frac{nM-\\lambda}{n(1-\\lambda)}L^2T)$|Uni.|$\\surd$|$\\times$|$\\times$|$\\times$|\n| | | | | | | |\n\nwhere $\\lambda$ characterizes the properties of decentralized topology. \n\n**Table 2**\n\n| | | | | | | | |\n|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|\n|**Algorithm+Reference**|**Optimization bound**|**Step size**|**L**|**$\\theta$**|**$\\beta$**|**B.**|**$\\sigma$**|\n|**AD-SGD**[1]|$\\mathcal{O}((r+\\frac{C_{\\lambda}}{\\lambda^{t_0}}+\\frac{t_0}{M})(\\log T)^{-1})$|$\\eta_t=\\mathcal{O}(\\frac{Mc}{t+1})$|$\\surd$|$\\times$|$\\surd$|$\\times$|$\\times$|\n|**AD-PSGD**[2]|$\\mathcal{O}(T^{-1/2})$|$\\eta_t=\\mathcal{O}(\\frac{n}{b_1(\\sqrt{T}+1)})$|$\\times$|$\\times$|$\\surd$|$\\times$|$\\surd$|\n| | | | | | | | |\n\nwhere $C_{\\lambda}=\\frac{4}{\\lambda e^2\\log\\lambda^{-1}}+\\frac{2}{\\lambda\\log\\lambda^{-1}}$.\n\n[1]X. Deng, et al. Stability-based generalization analysis of the asynchronous decentralized SGD. AAAI, 2023.\n\n[2]X. Lian, et al. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.\n***\n**Q2:** ... provide empirical experiments ...\n\n**A2:** There are some works providing some relevant experiments on FedZO [3]. For the asynchronous version, many related work [4][5] validates that the asynchronous strategy can take full advantage of the clients computation capabilities. It should be noted that our major contribution is exploring the theoretical generalization guarantee of federated zeroth-order optimization algorithm which is a gap as far as we know, especially for the stability-based analysis. Our theoretical results conform to these empirical behaviors [3] from both generalization and optimization perspectives which are listed as follows. \n\n**Generalization:** Our generalization bounds (Theorems 2, 3) are negatively correlated with the number M of selected clients at each iteration (the dependence $\\frac{1}{M}$ can be seen in lines 41 and 56 in Appendix), which is consistent with Figures 1(b) and 4 of [3].\n\n**Optimization:** Our optimization bounds (Theorems 4 and 6) are negatively correlated with the total iteration number $T$, which is presented in all figures of [3].\n\nTo further explicitly show the efficiency of the asynchronous version, some necessary experiments (similar to the ones of synchronous FedZO [3]) will be conducted later. We have utilized “global response” to provide Figure 1 to show the structure of asynchronous FedZO.\n\n[3]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[4]X. Lian, et al. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.\n\n[5]X. Lian, Y. Huang, Y. Li, and J. Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. NIPS, 2015.\n***\n**Q3:** ... provide more intuition behind the on-average model stability ...\n\n**A3:** Compared with other tools including uniform convergence, algorithmic stability enjoys the dimension-independence of hypothesis parameter space [6][7]. We list the advantages of on-average model stability over several other stability tools as follows [8]:\n\n**Vs. Uniform (model) stability:** On-average model stability is a weaker stability tool than uniform (model) stability.\n\n**Vs. On-average stability:** On-average model stability measures the stability of model parameters $w$ instead of function values $f(w)$, which can improve our analysis.\n\nMore comparisons among stability tools can be found in Appendix C of [9]. We have added the above statements in line 137 of the main paper.\n\n[6]W. Rogers et al. A finite sample distribution-free performance bound for local discrimination rules. The Annals of Statistics, 1978.\n\n[7]L. Devroye et al. Distribution-free performance bounds for potential function rules. TIT, 1979.\n\n[8]Y. Lei et al. Fine-grained analysis of stability and generalization for stochastic gradient descent. ICML, 2020.\n\n[9]J. Chen, et al. On the Stability and Generalization of Triplet Learning. AAAI, 2023.\n***\n**Q4:** ... provide some practical examples and how their results used?\n \n**A4:** Our theoretical results conform to the related experimental results of FedZO in [10]. Please see **Q2** for some examples. In addition, our results are also consistent with some distributed zeroth-order optimization algorithms, e.g., [11]. \n\n[10]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[11]E. Kaya, et al. Communication-efficient zeroth-order distributed online optimization: Algorithm, theory, and applications. Access, 2023.\n***\n**Q5:** ... how their results could be used in practice ...\n\n**A5:** Firstly, from the perspective of generalization theory, our results are consistent with the experimental results of previous work [12]. Secondly, from the perspective of practical application, our results can provide guidance for parameter choices (e.g. the number M of selected clients at each iteration, the total iteration number T and the step size $\\mu$ of gradient estimate) under some special accuracy requirement.\n\n[12]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022."}, {"review_id": "UtZbWscCwA", "reviewer": "Reviewer_YCFd", "summary": "The analysis of Federated Zeroth-Order Optimization is limited now. This work considers the zeroth-order optimization in federated learning and establishes the generalization error bound of FedZO under the Lipschitz continuity and smoothness conditions. ", "questions": "1. Could you provide more motivation to study zeroth-order optimization in federated learning? In practice, we have many stochastic optimizers in federated learning. Does zeroth-order optimization have any advantage compared with these optimizers? \n\n2. What is the key challenge of zeroth-order optimization in federated learning compared with the optimization in the single-machine setting?", "limitations": "No experiments are provided to verify their theoretical analysis", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The analysis of Federated Zeroth-Order Optimization is limited now. This work provides generalization bounds with theoretical analysis and asynchronous FedZO.\n", "weaknesses": "There is no experimental analysis. \n\n1. In deep learning, the first-order stochastic optimizer is very popular. Although some cases are mentioned where gradient information is expensive to obtain, it is necessary to use experiments to verify the necessity of the zero-order algorithm. \n\n2. Experiment about the efficiency of algorithms are also missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** ... it is necessary to use experiments to verify the necessity of the zero-order algorithm.\n\n**A1:** Thanks for your constructive comments. As your mentioned, there are some cases where gradient information is expensive to obtain and even unavailable [1], such as federated hyperparameter tuning [2] or distributed black box attack of deep neural networks (DNN) [3]. First-order optimizer is not suitable for these cases, which had been validated in many previous work [4][5][6].\n\n[1]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[2]Z. Dai, et al. Federated bayesian optimization via thompson sampling. NeurIPS, 2020.\n\n[3]X. Yi, et al. Zeroth\u0002order algorithms for stochastic distributed nonconvex optimization. arXiv, 2021.\n\n[4]J. Nocedal and S. Wright, Numerical optimization, Springer Science & Business Media, 2006.\n\n[5]A. Conn, et al. Introduction to derivative-free optimization, SIAM, 2009.\n\n[6]L. Rios and N. Sahinidis. Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 2013.\n***\n**Q2:** Experiment about the efficiency of algorithms are also missing.\n\n**A2:** Thanks. Some relevant experiments on FedZO had been provided in [7]. In addition, for the asynchronous version, there are many related works [8][9] validating that the asynchronous strategy can take full advantage of the clients computation capabilities. It should be noted that, as far as we know, there is a gap in the theoretical generalization guarantee of federated zeroth-order optimization algorithm, especially for the stability-based analysis, and our major contribution is providing the related stability-based theoretical generalization analysis. Our theoretical results conform to these empirical behaviors [7][8][9] from both generalization and optimization perspectives which are listed as follows. \n\n**Generalization:** Our generalization bounds (Theorems 2, 3) are negatively correlated with the number M of selected clients at each iteration (the dependence $\\frac{1}{M}$ can be seen in lines 41 and 56 in Appendix). It is consistent with Figures 1(b) and 4 of [7].\n\n**Optimization:** Our optimization bounds (Theorems 4 and 6) are negatively correlated with the total iteration number $T$, which is presented in all figures of [7].\n\nTo further explicitly show the efficiency of the asynchronous version, some necessary experiments (similar to the ones of synchronous FedZO [7]) will be conducted later. We have utilized “global response” to provide Figure 1 to show the structure of asynchronous FedZO.\n\n[7]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[8]X. Lian, et al. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.\n\n[9]X. Lian, Y. Huang, Y. Li, and J. Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. NIPS, 2015.\n***\n**Q3:** Could you provide more motivation to study zeroth-order optimization in federated learning? ... Does zeroth-order optimization have any advantage compared with these optimizers?\n\n**A3:** This paper aims to fill the gap in the generalization guarantee of zeroth-order optimization in federated learning, which is valuable to the development of related algorithms. Compared with many other stochastic optimizers in federated learning, zeroth-order optimization algorithm can tackle some special cases with unknown gradient information [10] (e.g., federated hyperparameter tuning [11] or distributed blackbox attack of DNN [12]) and achieve satisfactory performance (e.g., FedZO can serve as a satisfactory alternative for the FedAvg algorithm [10]).\n\n[10]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[11]Z. Dai, et al. Federated bayesian optimization via thompson sampling. NeurIPS, 2020.\n\n[12]X. Yi, et al. Zerothorder algorithms for stochastic distributed nonconvex optimization. Automatica, 2022.\n***\n**Q4:** What is the key challenge of zeroth-order optimization in federated learning compared with the optimization in the single-machine setting?\n\n**A4:** In federated learning, multiple clients use their own data to train a global model. Thus, the key challenge compared with single-machine learning is how to tackle the relationship among all clients, especially for the asynchronous version. We deal with it by introducing new formulas of the update of FedZO and asynchronous FedZO (see Equation (4) in Appendix B.3 and Equation (9) in Appendix B.5), and designing a new error decomposition strategy (see line 271). Besides, the unavailability of gradient information leads to another key challenge, i.e., estimating the real gradient of loss function. In this paper, we use the standard finite difference method to estimate the gradient and the second order Taylor expansion to make an approximation, respectively. Following your constructive comments, we have added a remark in line 118 of the main paper to demonstrate the above statements."}, {"review_id": "Tc0Juh3iqm", "reviewer": "Reviewer_obsy", "summary": "This paper provides generalization analysis of federated zeroth order optimization.", "questions": "Theory:\n- Line 105: what is the intuitive reason for the requirement $b_2 \\geq d$?\n- In (3), aren't we considering multiple local steps at the clients?\n- In (5), shouldn't there be an additional difference $\\mathbb E[F_S(w(S))] - F(w^*)$?\n- In the paragraph following Theorem 1 in lines 187-88, it is said that $\\mathbb E[F_S(A(S))]$ has no adverse impact on the upper bound. Why so? If this term is not close to zero, doesn't it introduce a bias, irrespective of $\\epsilon$?\n- Line 206: one can always find constant $c$ such that $\\beta c \\geq 1$ holds. Shouldn't there be some more conditions for this statement to hold?\n- Line 228 \"while introducing the dependence $(nN)^{-1}$\": but theorem 2 also has $(nN)^{-1}$\n- Line 249: what is $\\alpha$ in this bound?\n- Are all the results stated assuming full-client participation, since only $N$ appears in the bounds, even though (3) is with partial client participation ($M$).", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and addresses a relevant problem. The theoretical results appear correct, although I haven't thoroughly checked them.", "weaknesses": "Since I'm not super familiar with this direction, I just have a few clarification questions I have asked below. The one limitation in my opinion is the lack of multiple-local updates at the clients.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** Line 105: what is the intuitive reason for the requirement $b_2\\geq d$?\n\n**A1:** Thanks for your constructive comments. The requirement $b_2\\geq d$ is adopted by many previous work. For example, as mentioned in the second paragraph of Introduction in [1], “deterministic zeroth-order approaches require at least $b_2\\geq d+1$ queries”. In Section 3.3 of [2], the objective function is also evaluated $2d$ times to estimate gradients of all $d$ coordinates ($b_2=2d$). We have modified our explanation in line 105 of the main paper. \n\n[1] K. Nikolakakis, et al. Black-box generalization: Stability of zeroth-order learning. NeurIPS, 2022.\n\n[2] P. Chen, et al.  Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. AISec, 2017.\n***\n**Q2:** In (3), aren't we considering multiple local steps at the clients?\n\n**A2:** Due to some obstacles of proof technology, we don’t expand our analysis to the multiple-local case (H>1). If these obstacles are overcome in the future, we will further analyze the case you mentioned.\n***\n**Q3:** In (5), shouldn't there be an additional difference $\\mathbb E[F_S(w(S))] - F(w^*)$?\n\n**A3:** The complete form of Equation (5) should be $\\mathbb{E}[F(A(S))-F(w^*)]\\leq \\mathbb{E}[F(A(S))-F_S(A(S))]+\\mathbb{E}[F_S(A(S))-F_S(w(S))]$ since $\\mathbb{E}[F_S(w(S))-F(w^*)]=F(w(S))-F(w^*)\\leq 0$. To avoid ambiguity, we have corrected it with the complete inequality. \n***\n**Q4:** ... Why $\\mathbb E[F_S(A(S))]$ has no adverse impact on the upper bound? If this term is not close to zero, doesn't it introduce a bias, irrespective of $\\epsilon$?\n\n**A4:** Thanks. In this paper, we assume the output global model has a small empirical risk [3][4] on the training set to study the theoretical generalization performance on the unknown testing set. If this term $\\mathbb E[F_S(A(S))]$ is not small enough, we don’t wish that the performance on the training set is generalized to the unknown testing set. Thus, we let the term $\\mathbb E[F_S(A(S))]=\\mathcal{O}(1/(nN))$. An explanation has been added in the paragraph following Theorem 1.\n\n[3] Y. Lei et al. Fine-grained analysis of stability and generalization for stochastic gradient descent. ICML, 2020.\n\n[4] S. Li, Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. ICML, 2022.\n***\n**Q5:** Line 206: one can always find constant $c$ such that $\\beta c\\geq 1$ holds. Shouldn't there be some more conditions for this statement to hold?\n\n**A5:** These results [5][6][7] in Table 1 are not concise due to some parameters, such as $\\beta$ and constant c. Our results can’t be directly compared with them. Thus, we select some specific cases, (e.g., $\\beta c \\geq 1$ ) to show the advantage of our results, which is a standard strategy for comparisons of error bounds (see e.g., Table 1 in [8], Table 1 in [9]). We can’t ensure that one can always find constant $c$ such that $\\beta c \\geq 1$ holds. Following your valuable comments, we have added a remark for the parameter conditions in line 206 of the main paper.\n\n[5] M. Hardt, et al. Train faster, generalize better: Stability of stochastic gradient descent. ICML, 2016.\n\n[6] W. Shen, et al. Stability and optimization error of stochastic gradient descent for pairwise learning. arXiv, 2019.\n\n[7] K. Nikolakakis, et al. Black-box generalization: Stability of zeroth-order learning. NeurIPS, 2022.\n\n[8]W. Fang, et al. Communication-efficient stochastic zeroth-order optimization for federated learning. TSP, 2022.\n\n[9] K. Nikolakakis, et al. Black-box generalization: Stability of zeroth-order learning. NeurIPS, 2022.\n***\n**Q6:** Line 228 \"while introducing the dependence $(nN)^{-1}$\": but theorem 2 also has $(nN)^{-1}$\n\n**A6:** When we don’t take some specific value of $\\mu$, the order of Theorem 3 is $\\mathcal{O}(((nN)^{-1}\\sqrt{\\log T}+1)\\mu T^{\\frac{1}{2}}\\log T)$. Compared with Theorem 2, the bound in Theorem 3 is independent of Lipschitz parameter. Meanwhile, the dependence on $\\mu$ is improved from the partial dependence $(L/(nN) + \\mu)$ to full dependence $((\\sqrt{\\log T}/(nN) + 1) \\mu)$. We have corrected this statement in line 28 of our main paper.\n***\n**Q7:** Line 249: what is $\\alpha$ in this bound?\n\n**A7:** $\\alpha$ is the parameter of PL condition (Assumption 3 in lines 171 and 172 of the main paper).\n***\n**Q8:** Are all the results stated assuming full-client participation, since only $N$ appears in the bounds, even though (3) is with partial client participation ($M$).\n\n**A8:** Firstly, synchronous FedZO is with partial client participation. During the whole training process, there is a probability $\\frac{M}{N}$ for each client at each iteration to be selected to update the global model, which is the reason why $N$ appears in our bounds. While, for a single iteration, only M clients are used to update the global model. In fact, our bounds would have the dependence $\\frac{1}{M}$ if the term $\\frac{M}{N}$ is relaxed to 1 due to $M\\in[1, N]$. The details can be found in the proofs of Theorems 2, 3 (see lines 41 and 56). Secondly, asynchronous FedZO is with full-client participation, which is presented in Equation (7) of the main paper."}]

Author rebuttal:
Thanks for the comments of all reviewers. Considering the limitation of character count, we provide two figures and three tables in "global response". 

Figure 1 denotes the structure of the asynchronous FedZO algorithm.

Figure 2 denotes some sub-Weibull survival curves with varying tail parameters $\theta$ inspired by [3].

Table 1 denotes some new comparisons with the stability-based generalization bounds of asynchronous optimization algorithms [1].

Table 2 denotes some new comparisons with the optimization bounds of asynchronous optimization algorithms [1][2].

Table 3 denotes some new comparisons with the optimization bounds of distributed zero-order optimization algorithms [6][7].

**Table 1**
| | | | | | | |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
|**Algorithm+Reference**|**Generalization bound**|**Tool**|**L**|**$\theta$**|**$v^2$**|**B.**|
|**AD-SGD**[1]|$\mathcal{O}(\frac{n-\lambda}{n(1-\lambda)}(1+\frac{\beta \eta_1 }{M})^T)$|Uni.|$\surd$|$\times$|$\times$|$\times$|
|**AD-SGD**[1]|$\mathcal{O}(\frac{nM-\lambda}{n(1-\lambda)}L^2T)$|Uni.|$\surd$|$\times$|$\times$|$\times$|
| | | | | | | |

**Table 2**
| | | | | | | | |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
|**Algorithm+Reference**|**Optimization bound**|**Step size**|**L**|**$\theta$**|**$\beta$**|**B.**|**$\sigma$**|
|**AD-SGD**[1]|$\mathcal{O}((r+\frac{C_{\lambda}}{\lambda^{t_0}}+\frac{t_0}{M})(\log T)^{-1})$|$\eta_t=\mathcal{O}(\frac{Mc}{t+1})$|$\surd$|$\times$|$\surd$|$\times$|$\times$|
|**AD-PSGD**[2]|$\mathcal{O}(T^{-1/2})$|$\eta_t=\mathcal{O}(\frac{n}{b_1(\sqrt{T}+1)})$|$\times$|$\times$|$\surd$|$\times$|$\surd$|
| | | | | | | | |

**Table 3**
| | | | | | | | |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
|**Algorithm+Reference**|**Optimization bound**|**Step size**|**L**|**$\theta$**|**$\beta$**|**B.**|**$\sigma$**|
|**EF-ZO-SGD**[6]|$\mathcal{O}((d/T)^{1/2} + d/T)$|$\eta_t=\mathcal{O}(1/\sqrt{dT})$|$\surd$|$\times$|$\surd$|$\times$|$\times$|
|**FED-EF-ZO-SGD**[6]|$\mathcal{O}((d/T)^{1/2} + (d/T)^{3/2})$|$\eta_t=\mathcal{O}(1/\sqrt{dT})$|$\surd$|$\times$|$\surd$|$\times$|$\times$|
|**Distributed ZO Primal–Dual**[7]|$\mathcal{O}((d/(MT))^{1/2})$|$\eta_t=\mathcal{O}(d^{-1/2}(t+d^{1/(2\theta)})^{-\theta})$|$\times$|$\times$|$\surd$|$\times$|$\surd$|
| | | | | | | | |

[1]X. Deng, et al. Stability-based generalization analysis of the asynchronous decentralized SGD. AAAI, 2023.

[2]X. Lian, et al. Asynchronous decentralized parallel stochastic gradient descent. ICML, 2018.

[3]M. Vladimirova, et al. Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions. Stat, 2020.

[6]E. Kaya, et al. Communication-efficient zeroth-order distributed online optimization: Algorithm, theory, and applications. Access, 2023.

[7]X. Yi, et al. Zerothorder algorithms for stochastic distributed nonconvex optimization. Automatica, 2022.

Meta-review: This paper presents a fine-grained theoretical analysis of federated zeroth-order optimization techniques. The discussion phase improves everyone's understanding about this paper and we hope the authors revise it according to the reviewers' suggestion for the final version.
Decision: Accept (poster)