Zeroth-Order Methods for Nondifferentiable, Nonconvex, and Hierarchical Federated Optimization
Authors: Yuyang Qiu
Uday Shanbhag
Farzad Yousefian
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated Learning
Nonsmooth Optimization
Nonconvex Optimization
Bilevel Optimization
TL;DR: This work provides provably convergent zeroth-order methods for hierarchical federated learning.

Abstract: Federated learning (FL) has emerged as an enabling framework for communication-efficient decentralized training. We study three broadly applicable problem classes in FL: (i) Nondifferentiable nonconvex federated optimization; (ii) Federated bilevel optimization; (iii) Federated minimax problems. Notably, in an implicit sense, both (ii) and (iii) are instances of (i). However, the hierarchical problems in (ii) and (iii) are often complicated by the absence of a closed-form expression for the implicit objective function. Unfortunately, research on these problems has been limited and afflicted by reliance on strong assumptions, including the need for differentiability and L-smoothness of the implicit function. We address this shortcoming by making the following contributions. In (i), by leveraging convolution-based smoothing and Clarke’s subdifferential calculus, we devise a randomized smoothing-enabled zeroth-order FL method and derive communication and iteration complexity guarantees for computing an approximate Clarke stationary point.  To contend with (ii) and (iii), we devise a unified randomized implicit zeroth-order FL framework, equipped with explicit communication and iteration complexities. Importantly, our method utilizes delays during local steps to skip making calls to the inexact lower-level FL oracle. This results in significant reduction in communication overhead when addressing hierarchical problems. We empirically validate the theory on nonsmooth and hierarchical ML problems.

Zeroth-Order Methods for Nondifferentiable, Nonconvex, and Hierarchical Federated Optimization
Yuyang Qiu Dept. of Industrial and Systems Engg. Rutgers University
Uday V. Shanbhag
Dept. of Industrial and Manufacturing Engg. Pennsylvania State University
yuyang. qiu&rutgers.
udaybag@psu. edu
Farzad Yousefian
Dept. of Industrial and Systems Engg.
Rutgers University
farzad. yousef an@rutgers edu
Abstract
Federated learning (FL.) has emerged as an enabling framework for communication- efficient decentralized training. We study three broadly applicable problem classes in FL: (i) Nondifferentiable nonconvex federated optimization; (ii) Federated bilevel optimization; (iii) Federated minimax problems. Notably, in an implicit sense, both (ii) and (iii) are instances of (i). However, the hierarchical problems in (ii) and (iii) are often complicated by the absence of closed-for expression for the implicit objective function. Unfortunately, research on these problems has been limited and afflicted by reliance on strong assumptions, including the need for differentiability and L-smoothness of the implicit function. We address this shortcoming by making the following contributions. In (i), by leveraging convolution-basee smoothing and Clarke's 's subdifferential calculus, we devise a zeroth-order FL method and derive communica- tion and iteration complexity guarantees for computing an approximate Clarke stationary point. To contend with (ii) and (iii), we devise a unified randomized implicit zeroth-order FL framework, equipped with explicit communication and iteration complexities. Importantly, our method utilizes delays during local steps to skip making calls to the inexact lower-level FL oracle. This results in significant reduction in communication overhead when addressing hicrarchical problems. We empirically validate the theory nonsmooth and hierarchical MI. problems.
randomized smoothing-enst
Introduction
Federated learning (FL) has recently emerged as promising enabling framework for learning predictive models from a multitude of distributed, srivacy-sensitvve and possibly, heterogeneous datasets. This is accomplished through the use of efficiently devised periodic communications between a central server and a collection of clients. The FL algorithmic framework allows for addressing several key obstacles in the development and implementation of standard machine learning methods in a distributed and parallel manner. For instance, the conventional parallel stochastic gradient descent (SGD) method requires the exchange of information among the computing nodes at every single time step, resulting in excessive communication overhead. contrast, FL methods including FedAvg [34] and Local SGD [46] overcome this onerous communication bottleneck by provably attaining the linear speedup of parallel SGD by using a significantly fewer communication These guarantees have been further complemented by recent efforts [26
rounds 18
54
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

38 where the presence of both data heterogeneity (i.e,, variability of local datasets) and device heterogeneity (i.e., variability of edge devices in computational power, memory, and bandwidth) have been addressed. Despite recent advances, much needs to be understood about designing communication-effiice decentralized methods for resolving three broadly applicable problem classes, each of which is presented next.
(a) Nondifferentiable nonconvex locally constrained FL. Consider the prototypical FL setting:
f(x) f(t) {
min
- Σ B...p, X
n x
(FL..)
where f is nonsmooth nonconvex function and is associated with a group of m clients indexed by i E [m]] _ [l...., ..4...,,,,, m). D; denotes the local dataset, f; R" x D, + R is the local loss function, and X, S RR" an easy-to-project local constraint set. Notably, local datasets may vary across clients, allowing for data heterogeneity. We also consider client- alient-specffic local sets to induce personalization.
(b) Nondifferentiable nonconvex bilevel FL. Overlaying bilevel term in
F P
leads
1 E GED
min # X - M
f(x u(z) E arg min WER
(FL.)
X;
where f(o) - E ED, ( ( y (()))))) denotes the implicit objective function and y(+) R" - R a single-valued map returning the unique solution to the lower-level problem at a.
(c) Nondifferentiabbee nonconvex minimax FL. Finally, we consider the minimax setting, defined as
min =xX X, HER
max
m EE..
(FLmm)
where we assume that y(x) E arg maxyERa E. B,ED, (,,,, v. E:)] is unique for all x. Let f()) - E (()),))) denote the implicit objective function. Indeed, prob- lem FL subsumes this minimax formulation when we choose h4 == -f; and D; DD
Notably, in an implicit sense, both (b) and (c) are instances of problem (a). However, these hierarchical problems are often complicated by the absence of a closed-form form expression for the implicit objective, denoted by f()). Indeed, f()) is often nonsmooth, nonconvex, and unavailable. As such, the absence of both zeroth and first-order information of f()) in problems (b) and (c) makes the design and analysis of FL methods for these problems more challenging than that for (a).
Gaps. To the best of our knowledge, there are no known efficient FL algorithms that can contend with both nonsmoothness and nonconvexity in an unstructured sense. Generalizations that can accommodate either a bilevel or minimax structure also remain unaddressed in FL.
Goal. To develop a unified FL. framework accommodating nondifferentiable nonconvex settings with extensions allowing for bilevel or minimax interactions. We now describe the proposed framework.
1.1 A Smoothed Sampled Zeroth-order Framework
We consider a smoothed framework for contending with constrained, nonsmooth, and nonconvex regimes. Specifically, given that f is expectation-valued function and X is closed and convex set, both of which are defined in FF FL a smoothed unconstrained approximation is given as follows.
min DE Eg, f (x)
(min Em Ex (x.,
Ix. (z)
subject to x mm
Indicattor function
min E En, e Bl Eg. [fi(( + m74 El
Smoothing
(FL
Convolation smoothing
Moreau smontthng
If f is as defined in FF and d(x) A 1 Em Ix, (x), then f and its smoothing f are defined as
f(x) A f(x) d(x) and (x)) A (*)x)) + +d))
where (x) A 1 Bu, e Ex, (f. + m74, Ill and (x) & Σ K (T).

---

(i) Clarke-stationarity. Consider the original problem
Under the assumption that the objective of (FL Lipschitz continuous, then Clarke-staioonarit of z w.r.t (F requires that satisfies 0 E 0f (z) + Non,, (2)), where az()) represents the Clarke generalized gradient X of f at æ. However, negative result has been provided regarding the efficient computability of an c-stationary solution in nonsmooth nonconvex regimes [56]. Consequently, we focus on the smoothed counterpart (FL smooth nonconvex problem. In fact, under suitable conditions, it can be shown that stationary point of FFL uin is 27y-Clarke stationary point of the original problem, i.e.
[O (f) = [0 (x)))
(2)
where 0z (1:) represents the 211-Clarke generalized gradient of f a.
(ii) Meta-scheme for efficient resolution of FL We develop zeroth-order stochastic gradient schemes for resolving (FL nm This requires a zeroth-order gradient estimator for f*(x), denoted by
1 Σi=1 90((': (z. Si, 22)) where vú E r/S for i [m]] and S denotes the surface of the unit ball. Note that the Moreau smoothing of the indicator function of X,, denoted by 1xx (z). admits gradient, defined
as V.lx, (z) = # (zc Px, (z)). where Px, (x) - arg |y - æ=I?. The resulting meta- meta-scheme is yEX;
defined next.
2h+1 Ik 7 ? m E (o Es (1 + 1 (Ix Px, (=x))) k 0.
(Meta-ZO)
(iii) Inxxact implicit generalizations for F and FL FLam ) In addressing the bilevel problem, unlike in (F the clients in (FLs)) may not have access to the exact evaluation of the implicit local objective fi(0, g()))(()))))))))))) This makes a direct extension of FL schemes challenging. This is because the evaluation of the implicit local function necessitates exact resolution of the lower-level problem. We address this challenge by developing inexact implicit variants of the zeroth-order scheme, where clients compute only an e-approximation of y(r), denoted by (xr) in federated fashion. This inexact framework, described next, is crucial in addressing hierarchy in bilevel FL formulations. Let (o) denote the smoothed implicit local function. We estimate V (xx) by approximating the expectation by sampling in (a.1), as follows, while in (a.2). we replace y(æ) by an inexact form ys (z). This leads to the introduction of g. (x, v) as captured below.
(a.2)
V [zf((x)
Eg,, L9 (x, Eo, u)]
9f UT.)
g." (z, Es vT,),
cannot be tructably evaluated
intractable since u(x) is unavailable
where k is the local time index, T, the global time index of communication round r (k 2 T.), and (. - 2. (f + U. Ve +). v). - f, ye (z), e denotes an inexact implicit zeroth-order gradient. Note that at each round of communication at the upper level, ye (x) can be computed using calls to a standard FL method, e.g., FedAvg, in the lower level. Notably, such calls to an FL oracle should be made only at the global step to preserve the communication efficiency of the scheme. It follows that n.6 Ei Ur, = V f= (x) + êi where the approximation error és is a possibly biased random variable. This bias can be then controlled by carefully by updating the accuracy level E at each communication round, as we will address in this work.
1.2 Contributions
Our goal lies in extending (Meta-ZO) to federated nonsmooth nonconvex optimization and then provide generalizations bilevel and minimax regimes. each instance, we intend to provide iteration and point of the original problem. Accordingly, we make the following contributions.
coanmuuicaatioccoopple bounds for computing an e-accurate 17- -l-akk stationary
(i) Fl. for nondifferentiable nonconeex problems. To address (F with heterogeneous datasets, we develop Randomized Zeroth-Order Locally-Projected Federated Averaging method (FedRZO,... We derive iteration complexity of O m and communication complexity of O (m²3/ K3/4) for computing an approximate Clarke stationary point. Such guarantees appear to be new in the context of resolving nondifferentiable nonconvex FL problems, e.g. in training of ReLU neural networks (see T)ble This is distinct from existing zeroth- order methods, including FedZO [12, that rely on differentiability and L-smoothness of the local loss functions.
(ii) Federated bilevel optimization. In addressing (F we develop FedRZO.1. an inexact implicit extension of FedRZO,. By skipping local calls to the lower-level FL oracle, FedRZO,, is
3

---

Table Communication complexity for nonsmooth nonconvex, bilevel, and minimax FL problems. K and K denote the maximum number of iteration used in upper level and lower level, respectively.
helerggencous upper lovel (this wurk)
kower lovel (stamdani FL, schemms employed)
lotal bilevel and minimaa (this work)
(m)) 7) (Prop
Lid.. (Local SGD 30
O (m)
m
K
Thm
id.d (FedAC (
K
hederogeneous (LFD
3D
m R
o (mx) 12
novel communication-efficinn FL scheme with single-timescale local steps, resulting in significant reduction in communication overhead. T summarizes the communication complexity of this scheme. In all cases, we assume heterogeneous data at the upper level. the lower level, depending on which conventional FL scheme is employed, we obtain the communication complexity accordingly.
(iii) Federated minimax optimization. FedRZO,1 can be employed for addressing
F FLmm where
h2 = -s: As such, the complexity results in (ii) hold for solving (nondifferentiable nonconvex)- (strongly concave) FL minimax problems. Such results are new for this class of FL problems.
Remark 1. There has been recent progress in addressing bilevel and minimax problems in FL,
including Local SGDA and FedNest 48 43). Our work in (ii) and (iii) has two main distinctions with existing FL. methods, described as follows. (1) We do not require the differentiability and I.- smoothness of the implicit objective function. This assumption may fail to hold, e.g., in constrained hierarchical FL. problems. (2) The existing FL methods for bilevel and minimax problems assume that the lower-level problem is unconstrained. In fact, even in centralized regimes, addressing hierarchical problems where the lower-level constraints depend on x have remained challenging. For example, consider the problem mitlze[-1,a] maxye[-111,, #tyso x² + y that admits unique solution (x=,,"") yy" (0.5, -0.5). Now consider a reversal of min and max in this problem, i.e., max min =+y50 x² +y admitting the unique solution (a", yy" (-1, As consequence, the well-known primal-dual gradient methods, that have been extensively employed for addressing minimax problems with independent constraint sets, may fail converge to saddle-poii point in minimax problems with coupling constrains. Our proposed algorithmic framework allows for accommodating these challenging problems in FL.
2
Related work
Table 2: Comparison of our scheme with other FL. schemes for nonconvex settings
Noncumes
Meine
Rate
Comm, munds
Assmption
S3
Smooth
[Va1(a)12
Von
3/44
L-smooth fuactions
Brundal gradients
[V)1(x)]2
m
1/22)
L-smooth functions
Vuck
113
Smooth, PL-sond
f(x) f"
mx
m
1/1g
L-smooth functions, PL-condition
This work
Nonsmooth
(x)]"
Vonk
m 3(344)
Lipschitz functions
(i) Nondifferentiable nonconvex optimization. Nonsmooth and nonconvex optimization has been studied extensively with convergence guarantees to -tarke-stationary points via gradient sam- pling [22 and difference--f-cconee approaches [5]. Most complexity and rate guarantees necessitate
D 28 or convexity of the nonsmooth term [13], while only few results truly consider nonsmooth nonconvex objective function [32 4 42 (ii) Nondiffer- entiable nonconvex federated learning. The research FL. was initially motivated by decentralized neural networks where local functions are nondifferentiable and nonconvex (34 Nevertheless, theo-
smoothness of the nonconvex term [14 8
retical guarantees that emerged after FedAvg required either nonsmooth convex or smooth nonconvex local costs, under either iid [46, 588 50 47 or non-iid datasets [30 26). while provable guarantees for FL methods under nonconvexity (58 53 require L-smoothness of local functions. Unfortunately,
these assumptions do not hold either for ReLU neural networks or risk- aisereeerse learning and necessitate the use of Clarke calculus 3 Moreover, existing work on zeroth-order FL methods in convex [II and nonconvex settings [12 rely on the smoothness properties of the objective function. However, there appear to be no provably convergent FL schemes with complexity guarantees for computing approximate Clarke stationary points of nondifferentiable nonconvex problems. (iii) Federated
bilevel optimization. Hyperparameter tuning 21) and federated counterpart (23 crucial, and yet, computationally complex integrant of machine learning (ML) pipeline. Bilevel models

---

where the lower-level is a parameterized training model while the upper-level requires selecting the best configuration for the unknown hyperparameters [T]] 22 49 Solving such hierarchical problems is challenging because of nondifferentiable nonconvex terms and absence of an analytical form for the implicit objective. These challenges exacerbate the development of provable guarantees schemes. (iv) Federated minimax optimization. Minimax optimization has assumed relevance adversarial learning [17 40 44] and fairness in ML
for privacy-aware and communication-effice
[57], amongst other efforts. Recently FL was extended to distributed minimax problems [36 10 43)
but relatively little exists in nonconvex-strongly concave settings 48 43
3 A Zeroth-order FL Framework for Nondifferentiable Nonconvex Settings
In this section, we introduce our framework for (FLmn), where we impose the following assumption.
Assumption 1. Consider problem FLan D. The following hold.
(i The function Jü is Lipschitz continuous with parameter Lo > 0 for all E [m]]
(ii) For any i E [m], client has access to a zeroth-order oracle fi E,) satisfying the following for every x in an almost-sure sense:
(ii-a) (1, (.) x] fi(x);; (ii-b) There exists
such that B[I,(<,, f((x)1 a] u2.
(iii) The set X; is nonempty, closed, and convex for all E [m]. In addition, the following bounded set-dissimilarity condition holds for all x E _ and some scalars B1 and B2.
E m -i=1 dist (z. X₂) - B7 + + r- Em Px)
(3)
We note that the bounded set-dissimilarity condition is naturally analogous to the so-called bounded gradient-dissimilari condition that has been employed in the literature, c.g., in [25). In particular, when the bounded function of X,, denoted by 1, (z), we reach to (3). Notably, condition (3) holds for the generated iterates by the algorithm when, for example, the iterates remain bounded.
condition is stated for the Moreau smoothing of the indicator
Nonsmooth unconstrained reformulation. Consider unconstrained reformulation of FL given by min f(x:) (see (I). where the nonsmoothness of arises from that of f and the local indicator functions Tx,- The minimization of f is challenging, noted by recent findings on nonsmooth analysis where it is shown (56) that for a suitable class of nonsmooth functions, computing an e-stationary point, i.e., point for which dist(O.., (T)) S is impossible in finite time.
Approximate Clarke stationarity. To circumvent this challenge, as a weakening of e-stationarity, a notion of (8, -)statiionyrity is introduced [56] for vector 7 when dist(O,., (z)) S e, where the set
(xf(x) conv {c Ç E (f ||x vl S 5}
denotes the 5-Clarke generalized gradient of f at x [6] i.e. if x is (ō, e) ))-stationary, then there exists a convex combination of gradients in 6-neighborhood of æ that has a norm of at most 441.
This discussion naturally leads to the following key question: Can we devise provably convergent FL methods for computing approximate Clarke stationary points of minimization of The aim of this section is to provide an affirmative answer to this question by proposing a zeroth-order FL method that employs smoothing. To contend with the nonsmoothness, we employ the variant of Ix (I), where X 1 X,, and randomized smoothed variant of as shown next.
Randomized smoothing of loss function. To smoothen the loss function f. we employ a randomized smoothing approach where the smoothing parameter is maintained as sufficiently small. This
framework is rooted in the seminal work by Steklov (45). leading to progress in both convex [27 52)
I and nonconvex 377 regimes. We consider a smoothing f. given by f" defined as f() e
EueB[ [f ( + ryu)], where is a random vector in the unit ball R, defined as B - {u E R |u|] < 1). Further, we let denote the surface of the ball B, i.e., $ A {u E R" |||||| = 1} and nB and r/8 denote ball with radius 7) and its surface, respectively.
Lemma 1 (Randomized spherical smoothing). Let h R + R be given continuous function and define (x) e E.eB [h(x m4)]. Then, the following hold.
5

---

(i) h" continuously differentiable and (z) Evens (1 + +0) ||o for any x RR".
Suppose h is Lipschitz continuous with parameter Lo >> 0. Then, the following statements hold.
(ii (x*()) hn(2)) < Lo | yll for all 2, y R"; (iii) (x) h(x) - Lon for all R"; (iv)
[<) Vy)l Lon || yll for all y E IR".
The discussion leads to the consideration of the following smoothed federated problem.
Definition 1 (Unconstrained smoothed approximate problem). Given > 0, consider an uncon- strained smoothed problem given
min Fd (x) #ER"
- Ei (=)))(r))
} where f (x) e Eg (ff (x 7u4, E,) + 1 dist" (xx, X²).
2n
Algorithm 1 Randomizzd Zeroth-Order Locally-Projected Federated Averaging (FedRZO..)
1: input: Server chooses a random initial point to E X, stepsize " smoothing parameter synchronization indices To :- and T, 2 where 1 is the communication round index
2: for r = 0,... do
3: Server broadcasts è, all clients: FitT, == -r, Vi E [m)] do in parallel by clients Client generates the random replicates Ei, E Di and Us E n/S
4: for k = Tr..... , Tr+1
5:
9hxx = + (Pi C. fe( E..k)) Ug
6:
7: Client does local update as 21,4+1 = 2i,k
Ih + (ri - Px, (x(te))
8: end for
9: Server receives 21,7,41 from all clients and aggregates, i.e., ly41 == 1 m Dm T4TT441
10:
end for
To address we propose FedRZO.. given by Algorithm | Here, client i employs a zeroth-order
stochastic gradient of the form gh,- A xp [[((ts,x + Pi - [a Cr,s)) U1ks augmented by
the gradient of the Moreau smoothed function. The random sample 04 m/ is locally generated by each client i, allowing for randomized smoothing. This is indeed in view of Lemma (i) that facilitates the development of a randomized zeroth-order gradient.
We define 3 - #6.6
as auxiliary sequence to denote the averaged iterates of the clients.
m
Definition 2. Consider Algorithm T Let H > 0 denote upper bound on the number of local steps - T/I. Throughout, we assume that H/ is finite.
per round, i.e., 2 max
Proposition 1. Consider Algorithm
Let Assumption hold.
(i) [Error bound] Suppose 7 S min
Let k- denote an integer drawn
4Lon 477 (LonB(( f. uniformly at random from (0..... K} and fn* inf, (T))). Then,
V (e |P?] < (20))" + 12yLan 3 IK+1)
(20²
7 + Li)
mm
+ 2
Gn (n22
+ (3 + 4B,) LZn2
(ii) [[teration complexity] Let := / and H =
K m
where 17 > 0. Let c > be an arbitrary
scalar and K, denote the number of iterations such that E
("xx)) ) < c. Then, the iteration
complexity is K- : O (( Lon',²
Lgn²
+ Lgnto² 1
B
"
(iii) (Communication complexity] Suppose K, 2 m3 Then, the number of communication rounds to achieve the accuracy level in (ii) is == O (mmK))3/4).
We now formally relate the original nonsmooth problem and its smoothed counterpart.

---

Proposition 2. Consider problem and let Assumption hold.
(i) Assume that X, T for all i [m]- Then, for any 1 > 0, have (x) 02ns(x).
Assume that the sets X; are identical for all E [m]. Let å be an arbitrary scalar. 5 then O,, E Og (f +Ix (x) = and 1) max
4 Extensions to Bilevel and Minimax FL
4.1 Nondifferentiable nonconvex bilevel FL. In this section, consider the federated bilevel optimization problem defined earlier as (FLs)). We consider the following smoothed implicit problem.
Definition 3 (Unconstrained smoothed implicit problem). Given 17 > 0, consider an unconstrained
smoothed implicit problem given
min RER
f" (z)
Di=1 [EEE If: (xr nu, y( + mu), E.) dist (x, xi))}
(5)
m7
2n
Assumption 2. Consider problem FLag). p. Let the following assumptions hold.
(i) For all E [m]] fi(o, y, Ei) is L6 (G)) for any y and fi(x, " Es) is Lo (5:) Lipsshiz
max V /E((L, (G))²] < do and bg max for any v, where 1/ im iml....,m.
VEILL (s:)) < co.
im
(ii) For all E [m]]. for any h,(z,, .) is -1.yysmooth and μa -tsoonggly convex. Further, for any the map V (yh;(e.)) y) is Lipschitz continuous with parameter L (iii) The sets X,, for i [m], satisfy Assumption (iii.
The outline of FedRZOp1 is presented in Algorithm We make the following remarks: (i) At each global step, the server makes two calls a lower-level FL oracle inexactly compute y(č, + vT and y(.r). These lower-level FL calls are performed by the same clients, on the lower-level FL problem. (ii) The inexactness error is carefully controlled by terminating the lower-level FL oracle after (r)) number of iterations, where denotes the upper-level communication round index. (iii) FedRZO, skips the calls the lower-level FL oracle during the local steps. To accommodate this, unlike in FedRZO,.. m.s here we employ global randomized smoothing denoted by vr, during the communication round in the upper level.
Algorithm 2 Randomized Implicit Zeroth Order Federated Averaging (FedRZOb))
1: input: Server chooses random 2o X, stepsize y, smoothing parameter 1), synchronization indices To == 0 and T, 2 1, where r 2 is the upper-level communication round index
2: for 0, ..... do
3: Server generates a random replicate vr, E S
4: Server calls FedAvg to receive ys, (ft, + UT,) and ye, (f,). denoting the inexact evaluations
of yα, + uT,) and y(ž,), respectively.
5:
Server broadcasts ž,, &r UT Vs. (f,), and ye. (δ, VT.) to all clients; æ..r, Lr, Vi
6:
for k = . T - do in parallel by clients
7:
Client generates the random replicates Ei, E D;
8:
g = # (J( + ur, Me, (0, + Ur, ), ks,k) - [. Ne. (.x) vr.
Client does local update as rs,++1 = Fit 5 g:5r + (xi, Px, (Fi 10: end for
9:
11: Server receives 24,T,41 from all clients and aggregates, i.c., Zy41 == 1 Em Tt,T
m
12:
end for
Theorem 1 (FedRZOb) when using an arbitrary inexact FL method for lower-level). Consider Algorithm Let Assumption holld k* be chosen uniformly random from O,..., K := Tn
and < min
p n+1) Let E, denote the inexactness in
4H
24
obtaining the lower-level solution, i.c., E [llve, (x) v2))112 x]] E, for 12,, 2, + vT.).
7

---

(i) [Error bound] We have
E [ s (B71)) - (m))) 8, + 8 max f3)0s
+ 8 [ max 2 ,z}0, + 22) H r
where θ 31.g imp
n- n- 1)m²
(L O == 5( 12 Snj
1g :=
10,2
20n
(I )2
Hh
96n" 4 = xf²
(L and O₃ = 488; nf²
+ +96B3 + () lmp )
(ii) [Iteration complexity] Letry / and H ==
V
K m3
where 1) > 0. Let c > 0 be an arbitrary
scalar and Ke denote the number of iterations such that E ploy an FL method the lower level that achieves sublinear convergence rate with linear speedup where R, denotes the number of communica-
[ )[ S Also, suppose em-
in terms of the number clients, i.., Er == O TR
tion rounds performed in the lower-level FL method when is called in round of FedRZO,1 and 7 R. denotes the number of iterations performed in the lower-level FL scheme to do R, rounds of upper- level communication. Further, suppose Th. = Ô m 'r + 1)) Then, the iteration complexity of FedRZOp1 (upper level) is K, := Ô ((0} + max Oa]²0 max 0₂) + O me?
(iii) [Communication complexity] Suppose K, 2 m Then, the number of communication rounds in FedRZOpa (upper-level only) to achieve the accuracy level in (ii) is = O ((mK))8/)
Remark 2. (i) Importantly, Theorem [ is equipped with explicit communication complexity R == O ((mk))3/1) matching that of single-level nonsmooth nonconvex problems in Proposition | This implies that as long as the lower-level FL oracle has a rate of E, == O mi R.
). the inexactness does
not affect the communication complexity bounds of the method in the upper level.
(ii) As noted in the assumptions, in the upper level, allow for heterogeneity. To elaborate overall communication complexity FedRZOpa. we provide detailed complexity results in Table for three cases, where we employ Local SGD [26]. FedAC (54). and LFD (20 for the lower-level Notably, among these schemes, the last scheme allows for the presence of heterogeneity. As example, we present in
scheme. All these schemes meet the linear speedup condition in Theorem |
Algorithm g the outline of FedAvg, if employed in step 4 of Algorithm 2
Algorithm 3 FedAvg (I, r, ro m. 7, H, TR) for lower level
1: input: server chooses random initial point ûo = yo.r E RR == max(m, 4kh, r) + 1i,, where Ky P4 7 a,a, Tg. 2a, In(a,), and il TRa R
m
2: for 0, 1,1, 1,.,,.. R do
3: Server broadeasts ÓF to all agents: V, == Dr, Vi
4: for T,.... T++1 do in parallel by agents
5: Agent does local update as V1,++1 == Vi.t 7V (I,
6: Agent i sends TTTT, to the server
7: end for
8: Server aggregates, i.., 8p41 1 EEEBA
9:
end for
(ii) We use (Es) to denote the Lipschitz continuity constant of the random local implicit function
fe(z, ((),)()),,)) {i), and let imp A max;=1.....m V ([(LLi" (E:)) < oo. As shown in supplementary material, L (E,) can be obtained explicitly in terms of problem parameters.
Remark technical challenge in designing Algorithm is that an inexact evaluation y(r)) must be avoided during the local steps. This is because consider bilevel problems of the form FL

---

where both levels are distributed. Because of this, the inxxact evaluation of y(x) by each client in the local step in the upper level would require significant communications that is undesirable in the FL framework. We carefully address this challenge by introducing delayed inexact computation of v(a)). step of Algorithm 2 we note how Ye evaluated at ê, + "T, which a different than the vector used by the client, i.e., Li,k + "T, At each communication round in the upper level, we only compute ((x) inexactly twice in the global step and then use this delayed information in the local steps. This delayed inexact computation of renders a challenge in the convergence analysis which makes the design and analysis of Algorithm 2 a non-trivial extension of Algorithm [I
4.2 Nondifferentiable nonconvex-stroonlly concave minimax FL. Next, consider the decentral-
ized federated minimax problem of the form (FL (mmm introduced earlier. This problem is indeed a
zero-sum game and can be viewed as an instance of the non-zero sum game (FL where h4 == ʃz
Corollary 1. Consider Algorithm for solving ( Fmmm ). Let Assumption 2 hold for h2 == =- and
D. D... Then, all the results in Theorem hold true.
Experiments
We present three sets of experiments validate the performance of the proposed algorithms. In Section 5.1, we implement Algorithm [ on ReLU neural networks (NNs) and compare it with some recent FL methods. In Sections 5.2 and 5.3 we implement Algorithm 2 on federated hyperparameter learning and a minimax formulation in FL. Throughout, we use the MNIST dataset. Additional experiments on higher dimensional dataset (i.e., Cifar-10) 10) are presented in supplementary material.
Setting
(SI) with = 0.1
(S2) with 1) = 0.01
(S3) with rj 0.001
Log of average loss
-32
-22
step
-34
1.4
stepl
10 loca
-35
10 local
10 local steps
20 loral steps
Communication rounds
1E3 20
Communication rounds
200 do
890
edo
1000
Communication rounds
250 di
1000
Figure 1: Performance of FedRZO.. on a single-layer ReLU NN terms of communication rounds for different no. of local steps and different values of the smoothing parameter 1). FedRZO,. benefits from larger number of local steps and shows robustness with respect the choice of r).
5.1 Federated training of ReLU NNs. We implement FedRZO,. for federated training in a single-layer ReLUU NN with Nj neurons. This is nondifferentiable nonconvex optimization problem, aligning with FL and taking the form minz.=(Z.wexx
1 EE EtED, (Vi
2m
(11Z) + ||xll?), where m denotes the number of clients, 7 E RNN.NN,, w E N,, No is the feature dimension, U.. E R No and ūie E f-1, 1} are the 9th input and output training sample of client respectively, (z) == max(0, x). and X is the regularization parameter.
Eg (Z,g
Setup. We distribute the training dataset among m := 5 clients and implement FedRZO.. for the FL training with N1 == 4 neurons under three different settings for the smoothing parameter, 7 E {0.1, 0.01, 0.001), 7 := 10 5. and À ;= 0.01. We study the performance of the method under different number of local steps with H E 51,5, 10, 20).
Results and insights. Tigureppresente the first set of numerics for FedRZO... under the aforemen- tioned settings. In terms of communication rounds, we observe that the performance of the method improves by using larger number of local steps. In fact, in the case where H == 1, FedRZO,. is equivalent to parallel zeroth-order SGD that employs communication among clients at each iteration, resulting in poor performance, motivating the need for the FL framework. In terms of 7, while we observe robustness of the scheme in terms of the original loss function, we also note a slight improvement the empirical speed of convergence in early steps, as rj increases. This indeed aligned with the dependence of convergence bound in Proposition on 17.

---

Comparison with other FL methods. While we are unaware of other FL methods for addressing nondifferentiable nonconvex problems, we compare FedRZOn.. en with other FL methods including FedAvg [34], FedProx 29 FedMSPP [SS] and Scaffnew [35 when applied on NN with smooth rectifier. Details of these experiments are provided the supplementary material.
5.2 Federated hyperparameter learning. To validate FedRZOb1. we consider the following FL hyperparameter learning problem for binary classification using logistic loss.
f(z,8) - E EIED, log (1+ exp( exp(-v,,eU
min zex, VER"
m h(2, v) - - (EieD, log ( (x (,2 + x 1
subject to
y E arg min yER"
where m is number of clients, I denotes the regularization parameter for client i, Use E R and vse E {-1,1] 13 are the 7th input and output testing sample of client respectively, U3." R²" and wge E {-1,1} } are the ('th input and output training sample of client i, respectively. The constraint plm) where μ > This problem is instance of
X is considered as X {i E R (FLx). where the lower-level problem is éz-regularized and the regularization parameter is decision variable of the upper-level FL problem. The convergence results are presented in Fig. (left.
5.3 Fair classification learning, Here, we study the convergence FedRZO,1 in minimax FL. We consider solving an FL minimax formulation of the fair classification problem [9 of the form
min max =ER" yER*
SE EVED,, E
Ni Wg (Z. UZ, 1l/l
where denotes the class index and Di.. denotes the portion of local dataset associated with client that is comprised of class e samples. The loss function follows the same formulation in Section 5.1, where an ReLU neural network is employed. This problem is nondifferentiable and nonconvex-strone concave, fitting well with the assumptions in our work in addressing minimax FL problems. The performance our algorithm is presented in Figure 2 (right).
25
5000
H-20
6.0
1002
830
Figure 2: (Left) Convergence FedRZO in hyperparameter FL. for l regularized logistic loss, where we plot the loss function test data for different values of local steps with 95% Cls. (Right) Convergence of FedRZOp1 in minimax FL, where we present test results in solving nondifferentiable nonconvex-strongly concave FL minimax formulation of the fair classification problem (39
Concluding Remarks
Federated learning has assumed growing relevance in ML. However, most practical problems are char- acterized by the presence of local objectives, jointly afflicted by nonconvexity and nondifferentaabiliyy precluding resolution by most FL schemes, which can cope with nonconvexity in only smooth settings. We resolve this gap via zeroth-order communication efffccien FL framework that can contend with both nondifferentiability and nonsmoothness with rate complexity guarantees computing approximate Clarke-stationn concave minimax settings are developed via inexact generalizations.
points. Extensions to nonconvex bilevel and nonconvex-strongly
7 Acknowledgments
We acknowledge the funding support from the U.S. Department of Energy under grant #DE- SC0023303, and the U.S. Office of Naval Research under grants #200014-22-1-2757 and #N00014- 22- 22-1-2589. We also would like to thank the four anonymous referees for their constructive suggestions.
10

---

References
[1] J. V. Burke, A. S. Lewis, and M. L. Overton. Approximating subdifferentials by random sampling of gradients. Math. Oper. Res., 27(3):667-584, 2002.
[2] J. V. Burke, A. S. Lewis, and M. L. Overton. A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim., 15(3):751-77, 2005.
[3] H. Clarke. Generalized gradients and applications. Transactions of the American Mathemati- cal Society, 205:247-262, 1975.
[4] Cui, U. Shanbhag, and F. Yousefian. Complexity guarantees for an implicit smoothing- enabled method for stochastic mpecs. Math. Program., 198(2):1153-122) 2023.
[5] Y. Cui and S. Pang. Modern nonconvex nondifferentiable optimization, volume 29 of MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, [2022] @2022.
[6] S. Dafermos. Sensitivity analysis in variational inequalities. Mathematics of Operations Research, 13(3):421-34, 1988.
[7] R. Das, A. Acharya, A. Hashemi, S. Sanghavi, I. S. Dhillon, and U. Topcu. Faster non-convex federated learning via global and local momentum, 2021.
[8] D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Optim., 29(1):007-239 2019.
[9] D. Davis and B. Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM J. Optim., 29(3):1908-199) 2019.
[10] Y. Deng, M. M. Kamani, and M. Mahdavi. Distributionally robust federated averaging. In
H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15111-15122. Curran Associates, Inc., 2020.
[11] C. Duchi, P. Bartlett, and Martin J. Wainwright. Randomized smoothing for stochastic optimization. SIAM J. on Optimization, 22(2):674-701, 2012.
[12] W. Fang, Z. Yu, Y. Jiang, Y. Shi, C. Jones, and Y. Zhou. cummumication-effiieen stochastic zeroth-order optimization for federated learning. IEEE Transactions on Signal Processing, 70:5058-500 2022.
[13] A. Gasnikov, A. Novitskii, V. Novitskii, F. Abdukhakimov, D. Kamzolov, A. Beznosikov, M. Takáë, P. Dvurechensky, and B. Gu. The power of first-order smooth optimization for black- box non-smooth problems. arXiv preprint arXiv: 2022.
[14] S. Ghadimi, G. Lan, and H. Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Math. Programming, 155(1-2):27-335,, 2016.
[15] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint: http://aaivv.orgg/ab/////.0000.0
[16] A. A. Goldstein. Optimization of Lipschitz continuous functions. Math. Programming, 13(1):14-
22, 1977.
[17] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[18] F. Haddadpour, M. M. Kamani, M. Mahdavi, and V. Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. Advances Neural Information Processing Systems, 32, 2019.

---

[19] F. Haddadpour, M. M. Kamani, M. Mahdavi, and V. Cadambe. Trading redundancy for Speeding up distributed SGD for non-convex optimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2545- 2554. PMLR, 09-15 Jun 2019.
communication:
[20] F. Haddadpour and M. Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint arXiv:1910. 14425, 2019.
[21] E. Hazan, A. Klivans, and Y. Yuan. Hyperparameter optimization: A spectral approach. 6th International Conference on Learning Representations (ICLR), 2018.
[22] K. Ji. J. Yang, and Y. Liang, Bilevel optimization: Convergence analysis and enhanced design. arXiv preprint: https//aaxxvorry/p/2222000002102
[23] Kairouz, H. Brendan McMahan, et al. Advances and open problems in federated learning. CoRR, abs/1912.04977, 2019.
[24] S. P. Karimireddy, M. Jaggi, S. Kale, M. Mohri, S. J. Reddi, S. U Stich, and A. T. Suresh. Break- ing the centralized barrier for cross-device federated learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[25] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[26] A. Khaled, K. Mishchenko, and P. Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529, PMLR, 2020.
[27] H. Lakshmanan and D. Farias. Decentralized recourse allocation in dynamic networks of agents. SIAM Journal on Optimization, 19(2):911-940, 2008.
[28] J. Lei and U. V. Shanbhag. Asynchronous variance- reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes. Opti- mization Methods and Software, pages 1-31, 2020.
[29] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 1:429-450, 2020.
[30] X. Li, K. Huang, W. Yang. S. Wang, and Z. Zhang. On the convergence of FedAvg on Non-IID data. In International Conference on Learning Representatiinss 2020.
[31] Zan Li and Li Chen. Communication--fficeenn decentralized zeroth-order method on heteroge- neous data. In 2021 13th International Conference on Wireless Communications and Signal Processing (WCSP), pages 1-6. IEEE, 2021.
[32] Lin, 7. Zheng, and M. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160-26175, 2022.
[33] D. Q. Mayne and E. Polak. Nondifferential optimization via adaptive smoothing. Journal of Optimization Theory and Applications, 43(4):601-6) -613,, 1984.
[34] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Ciammunicatio-Efficcee Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 1273-1282. PMLR, 20-22 Apr 2017.
12

---

[35] K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 15769, PMLR, 17-23 Jul 2022.
[36] M. Mohri, G. Sivek, and A. T. Suresh. Agnostic federated learning. In International Conference on Machine Learming, pages 4615-4625. PMLR, 2019.
[37] Y. Nesterov and V. Spokoiny. Random gradient-free free minimization of convex functions. Found. Comput. Math., 17(2):527-566, 2017.
[38] J. Nguyen. K. Malik, H. Zhan, A. Yousefpour, M. Rabbat, M. Malek, and D. Huba. Federated learning with buffered asynchronous aggregation. CoRR, abs/2106.06634 2021.
[39] M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn. Solving a class of non- convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
[40] M. Sanjabi, J. Ba, M. Razaviyayn, and J. D. Lee. On the convergence and robustness of training gans with regularized optimal transport. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[41] O. Shamir. Can we find aperooxproi saroooiiimaeey-stttinaaryy points of nonsmooth nonconvex func- tions? In OPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2021.
[42] U. V. Shanbhag and F. Yousefian. Zeroth-order randomized block methods for constrained minimization of expectation-vallee lipschitz continuous functions. In 2021 Seventh Indian Control Conference (ICC), pages 7-12. IEEE, 2021.
[43] P. Sharma, R. Panda, G. Joshi, and P. Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. International Conference on Machine Learning, pages 19683-19730. PMLR, 2022.
[44] A. Sinha, H. Namkoong, and J. Duchi. Certifiable distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
[45] V. A. Steklov. Sur les expressions asymptotiques decertaines fonctions définies par les équations différentielles du second ordre et leers applications au problème du dévelopement d' l'u fonction arbitraire séries procédant suivant les diverses fonctions. Comm. Charkov Math. Soc., 2(10):77-19,, 1907.
[46] S. U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representationss 2019.
[47] S. U. Stich and S. P. Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. Journal of Machine Learning Research, 21:1-36, 2020.
[48] D. A. Tarzanagh, M. Li, C. Thrampoulidis, and S. Oymak. Fednest: Federated bilevel, minimax, and compositional optimization. In International Conference on Machine Learning, pages 21 146-21179. PMLR, 2022.
[49] R. Tibshirani, M. Saunders. S. Rosset, J. Zhu, and K. Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(1):91-108, 2005.
[50] J. Wang and G. Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. Journal of Machine Learning Research, 22(213):1-50, 2021.
[51] Y. Xu and W. Yin. A globally convergent algorithm for nonconvex optimization based on block coordinate update. Journal of Scientific Computing, pages 1-35, 2017.
13

---

[52] F. Yousefian, A. Nedić, and U. V. Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56 67, 2012.
[53] H. Yu, Yang, and Zhu. Parallel restarted SGD with faster convergence and less communi- cation: demystifying why model averaging works for deep learning. In AAAI Conference on Artificial Intelligence, 2019.
[54] H. Yuan and T. Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332-5344 2020.
[55] X. Yuan and P. Li. On convergence of fedprox: Local dissimilarity invariant bounds, non- smoothness and beyond. Advances in Neural Information Processing Systems, 35:10752-10765, 2022.
[56] Zhang. Lin, Jegelka, S. Sra, and A. Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 11173-11182. PMLR, 13-18 Jul 2020.
[57] L. Zhang, D. Xu, S. Yuan, and X. Wu. FairGAN: Faimess- generative adversarial networks. In CoRR, 2018.
[58] F. Zhou and G. Cong. On the convergence properties of a K-step averaging stochastic gra- dient descent algorithm for nonconvex optimization. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence 2018.
14


Reviews:
[{"review_id": "O8FcF8kOpU", "reviewer": "Reviewer_Lumm", "summary": "Existing federated optimization algorithms usually rely on the assumption of differentiability and smoothness, which may fail to hold in practical settings. To this end, this paper employs randomized smoothing approach and zeroth-order optimization techniques for the development of FedRZO algorithm to address this kind of problem. Theoretical analyses on convergence, iteration complexity and communication complexity have also been provided. This paper further extend the idea behind the newly developed algorithm to bilevel and minimax federated optimization problems with sound theoretical guarantees.", "questions": "1. What's the difference between line 6 of Algorithm 1 and the gradient estimation (or even the algorithm) in FedZO [R1]? They seem to share similar calculation with only different scale that has been multiplied.\n2. Are the baselines in Figure 2 able to access the gradient? If so, shouldn't they converge much faster compared with your zeroth-order optimization algorithm?", "limitations": "Limitations haven't been mentioned.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper has studied three different federated setting that existing works seldomly consider with both theoretical guarantees and empirical justifications.\n2. The combination of randomized smoothing technique with zeroth-order optimization appeals to me, which may inspires the future work on non-smooth zeroth-order optimization.\n3. Empirical results are interesting with adequate interpretation.", "weaknesses": "1. This paper may give more intuitive explanation or interpretation for its equations to ease reader's understanding. E.g., the authors may need to provide certain motivations for the study of the three different cases in the introduction section instead of directly putting out these cases without any explanation. Besides, the authors may also need to provide intuitive explanation for eq. 3 to help justify the reasonability of this assumption as well as its connection with real-world examples.\n2. This paper may need to compare with more federated optimization algorithms to verify the efficacy of their algorithms, e.g., SCAFFOLD, FedZO [R1], from both theoretical and empirical perspectives.\n\n[R1] Fang, Wenzhi, Ziyi Yu, Yuning Jiang, Yuanming Shi, Colin N. Jones, and Yong Zhou. 2022. “Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning.”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful suggestions and comments on improving this work.\n \n$\\textbf{Response to weakness 1:}$ Thank you for pointing this out. To be clear, the three formulations are all nondifferentiable nonconvex FL problems. The motivation for the three formulations is mentioned in lines 112--120 and 123--126 in section 2. The federated training of ReLU neural networks has coupled nondifferentiability and nonconvexity. In bilevel and minimax FL, the nondifferentiability and nonconvexity come from the implicit objective function. If the opportunity is provided, we will add more intuitive explanations on technical equations to smooth reader's experience. \n\nRegarding eq. (3), as we have noted in the paper, this is an instance of the bounded gradient dissimilarity in SCAFFOLD. Indeed, when the bounded gradient dissimilarity assumption in SCAFFOLD is written for the local functions $0.5\\Vert x-\\mathcal{P}_{X_i}(x)\\Vert^2$ we reach to eq. (3). Further, this assumption holds when for example the generated iterate by the algorithm remains bounded. We imposed this assumption to weaken the boundedness assumption.\n\n\n$\\textbf{Response to weakness 2:}$ We would like to point out that both these references assume $L$-smoothness of the local objectives. This is a strong assumption and it often fails to hold when considering bilevel problems. We don't make this assumption and only consider Lipschitz continuity of the objective function. Please note that the progression from smooth nonconvex to nonsmooth nonconvex leads to some challenges and necessitates the introduction of Clarke-stationarity. As we have noted in lines 144--147, our work in designing Algorithm 1 is motivated by recent findings where it is shown that for a subclass of nonsmooth nonconvex functions, computing an $\\epsilon$-stationary point is impossible in finite time.\n\n$\\textbf{Response to question 1:}$ We do agree that FedZO leverages a similar smoothing technique, however, it does not address bilevel problems. One of the key contributions in our work is the design of Algorithm 2 and its complexity analysis in Theorem 2. To clarify, consider the (centralized) bilevel minimization of $f(x,y(x))$ with respect to $x$ where $y(x) \\in \\hbox{arg}\\min_{y \\in \\mathcal{Y}(x)}\\ h(x,y)$. Even when $f$ is smooth and convex in $(x,y)$, the implicit function $f(\\bullet,y(\\bullet))$ is often nondifferentiable nonconvex in $x$. Second, the analytical form of $y(\\bullet)$ is unavailable in most ML applications. As such, $\\textbf{the zeroth-order information of the implicit function $f(\\bullet,y(\\bullet))$ is not available}$ and it is not clear how one can develop a provably convergent zeroth-order method for computing a stationary point to the nonsmooth nonconvex problem $\\min_{x}\\ f(x,y(x))$. A naive idea is to inexactly compute $y(x)$. However, an inexact computation of $y(x)$ leads to a bias in the approximation of the zeroth-order gradient. This $\\textbf{bias further propagates}$ throughout the implementation (see Theorem 2(i) where we manage to derive the aggregated bias as $\\sum_{r=0}^R{\\varepsilon_r}$). Importantly the bound in Theorem 2(i) implies that even when we inexactly compute $y(x)$ using a standard FL scheme, we are able to derive complexity guarantees for solving bilevel FL problems. \n\nPlease note that a major technical challenge we faced in designing Algorithm 2 is that $\\textbf{inexact evaluations of $y(x)$ must be avoided during the local steps.}$ This is because we consider bilevel problems where both the levels are distributed. Because of this, the inexact evaluation of $y(x)$ by each client in the local step in the upper level would require significant communications and is counter-intuitive to the nature of the FL framework. We carefully address this challenge by introducing delayed inexact computation of $y(x)$. See step 8 in Algorithm 2 and note how $y_{\\varepsilon}$ is evaluated at $\\hat x_r +v_{T_r}$ that is different than $x_{i,k} +v_{T_r}$. $\\textbf{This delayed inexact computation of $y$ renders some technical challenges}$ in the proofs and so, we hope that the design and analysis of Algorithm 2 are not viewed as simple extensions of existing zeroth-order methods. \n\nLastly, we hope to clarify the significance of the results in our paper and how they benefit the research on FL. Our work appears to be the first paper that provides an FL method with complexity guarantees for solving bilevel optimization problems where the $\\textbf{lower-level problem may be constrained.}$ There have been several recent works that have highlighted the challenges in solving this type of hierarchical problems (i.e., Stackelberg games), even in centralized settings. For example, consider $\\min_{x \\in [-1,1]}\\ \\max_{y \\in [-1,1],\\ x+y\\leq 0}\\ x^2+y$. The solution is $(x^*,y^*)=(0.5,-0.5)$. The same problem, but with a reversed order of min and max, $\\max_{y \\in [-1,1]}\\ \\min_{x \\in [-1,1], \\ x+y\\leq 0}\\  x^2+y$, has the solution $(x^*,y^*)=(-1,1)$. One of the major contributions in our work is that Algorithm 2 can be employed to address this challenging class of problems complicated with the need for federated learning in both levels. To provide more details on this, please see Remark 1 and Table 1 in our paper. We have provided explicit communication complexity results for addressing bilevel FL problems under use of different FL methods for the lower level problem. These are only a few instances of the breadth of FL problems that we can provably address using Algorithm 2.\n \n\n$\\textbf{Response to question 2:}$ Thank you for the question. They do have access to the gradient, however they seem to be sensitive to the choice of the parameter $\\beta$ in the scaled softplus function (differentiable) defined in line 270, larger $\\beta$ means more accurate approximation of the ReLU (nondifferentiable), and ReLU is what we used as the activation function. As shown in Figure 2, our algorithm shows more robustness."}, {"review_id": "YVoCvfQuJm", "reviewer": "Reviewer_CtdY", "summary": "**Summary:** The paper develops zero-th order methods for solving non-smooth and non-convex federated problems. In addition, the paper also develops zero-th order methods for solving bilevel and minimax optimization problems in a federated setting. The authors develop a randomized smoothing-based approach and present convergence guarantees for the proposed algorithms. Experiments on training ReLU neural networks and hyperparameter optimization tasks are presented to evaluate the performance of the proposed algorithms. ", "questions": "Please see the weakness section above. ", "limitations": "n/a", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Strengths:** The paper considers an important problem class of solving non-convex and non-smooth problems with zero-th order oracle. The paper is very well written with ideas explained clearly.  ", "weaknesses": "**Weaknesses:** Here, I list some points the authors should consider addressing:\n\n1.\tThere is some existing literature on federated learning where randomized smoothing-based zero-th order methods have already been developed. The authors have not mentioned/or compared their approach against such methods Please see [R1], [R2] (strongly convex) below. \n \n\n     [R1] Fang et al., Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning   \n\n     [R2] Li et al., Communication-efficient decentralized zeroth-order method on heterogeneous data\n\n\n2.\tThe authors should make dependence on the problem dimension explicit in the tables and the communication complexities listed in all the theorems. The current presentation gives an indication to the reader that zero-th order methods can achieve the same guarantees as first-order methods which is certainly not true.   \n\n3.\tThe authors should consider including some discussion on the bounded set dissimilarity since the assumption is relatively new in the context of FL. \n\n4.\tIs the notion of Clarke stationarity point related to Goldstein stationary point (or are the two notions the same)? Also, the discussion on Clarke's generalized gradient of the original problem compared to the gradient of the smoothed objective appears before the definition of Clarke's stationarity point. Please consider moving the definition before the discussion. \n\n5.\tIn Line 172 and Prop. 1 please characterize sufficiently small $\\eta$. \n\n6.\tTheorem 2 ignores the additional communication complexity because of solving the lower-level problem to $\\epsilon_r$ accuracy. The authors should report the complete communication complexity incurred by the algorithm for solving the bilevel optimization problem not only the upper-level complexity.  \n\n7.\tFinally, the experiments considered to evaluate Algorithm 1 are weak. Specifically, the authors have considered a very low-dimensional problem. It would be advisable to include training on Cifar-10/MINST datasets with practically sized neural networks to evaluate the actual performance of the proposed scheme. Moreover, for hyperparameter learning there are many baseline bilevel algorithms including BSA, TTSA, ALSET, SUSTAIN, stocBiO, etc. whose performance should be compared with the proposed scheme. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. We address the comments point by point as follows.\n \n$\\textbf{Response to weakness 1:}$ Note that [R1] considers smooth, but possibly nonconvex, problems while [R2] considers smooth and strongly convex problems. Several distinctions persist. (I) While some FL methods use a zeroth-order framework, they require differentiability or $L$-smoothness of the objective function in the convergence theory. (II) We do agree that these schemes leverage a similar smoothing technique, however, they don't address bilevel problems. One of our key contributions is the design of Algorithm 2 and its complexity analysis in Theorem 2. To clarify, consider the (centralized) bilevel minimization of $f(x,y(x))$ with respect to $x$ where $y(x) \\in \\hbox{arg}\\min_{y \\in \\mathcal{Y}(x)}\\ h(x,y)$. Even when $f$ is smooth and convex in $(x,y)$, the implicit function $f(\\bullet,y(\\bullet))$ is often nondifferentiable nonconvex in $x$. Also, the analytical form of $y(\\bullet)$ is unavailable in most ML applications. As such, $\\textbf{the zeroth-order information of the implicit function $f(\\bullet,y(\\bullet))$ is not available}$ and it is not clear how one can develop a provably convergent zeroth-order method for computing a stationary point to the nonsmooth nonconvex problem $\\min_{x}\\ f(x,y(x))$. A naive idea is to inexactly compute $y(x)$. However, this leads to a bias in the approximation of the zeroth-order gradient. This $\\textbf{bias further propagates}$ throughout the implementation (see Theorem 2(i) where we manage to derive the aggregated bias as $\\sum_{r=0}^R{\\varepsilon_r}$). Importantly the bound in Theorem 2(i) implies that even when we inexactly compute $y(x)$ using a standard FL scheme, we can derive complexity guarantees for bilevel FL. \n\nA major technical challenge we faced in designing Algorithm 2 is that $\\textbf{inexact evaluations of $y(x)$ must be avoided during the local steps.}$ This is because we consider bilevel problems where both the levels are distributed. So, the inexact evaluation of $y(x)$ by each client in the local step in the upper level would require significant communications and is counter-intuitive to the nature of the FL framework. We carefully address this challenge by introducing delayed inexact computation of $y(x)$. See step 8 in Algorithm 2 and note how $y_{\\varepsilon}$ is evaluated at $\\hat x_r +v_{T_r}$ that is different than $x_{i,k} +v_{T_r}$. $\\textbf{This delayed inexact computation of $y$ renders some technical challenges}$ in the proofs and so, we hope that the design and analysis of Algorithm 2 are not viewed as simple extensions of existing zeroth-order methods. \n \n$\\textbf{Response to weakness 2:}$ Your point on the dependence on $n$ is well-taken. We can also present the dependence on the smoothing parameter $\\eta$ in the complexity results. We will be happy to make this change if the opportunity is provided. However, we would like to emphasize that our major contribution in this work lies in addressing bilevel FL problems in absence of the analytical form of the lower level solution. This problem, even in very low dimensions, has remained challenging in FL. \n\n $\\textbf{Response to weakness 3:}$ Regarding eq (3), as we have noted in the paper, this is an instance of the bounded gradient dissimilarity in SCAFFOLD. Indeed, when the bounded gradient dissimilarity assumption in SCAFFOLD is written for the local functions $0.5\\|x-\\mathcal{P}_{X_i}(x)\\|^2$ we reach to eq. (3). Further, this assumption holds when for example the generated iterate by the algorithm remains bounded. We imposed this assumption to weaken the boundedness assumption.\n\n $\\textbf{Response to weakness 4:}$ Thank you. Goldstein also refers to Clarke stationary points. His contribution lies in showing that if $x$ is stationary with respect to the smoothed problem, then $x$ is $\\eta$-Clarke stationary with respect to the original problem. \n \n $\\textbf{Response to weakness 5:}$ Thank you for pointing this out. Our proof for this result has been omitted. In the revised version of our manuscript, we will be happy to make this change and provide the detailed proof.\n  \n $\\textbf{Response to weakness 6:}$  We actually did provide the explicit total communication complexity in Table 1 when three different lower-level algorithms are employed. The proof can be found in Appendix C. Also, in Thm. 2, we provide upper-level communication complexity because it is the algorithm for upper-level. Note that in Algorithm 2 line 4, \"FedAvg\" denotes the suitable federated averaging method for solving the lower level problem. \n\n $\\textbf{Response to weakness 7:}$ We thank the reviewer's suggestion on strengthening our experimental part. We will apply our methods on datasets with higher dimension. These algorithms are not federated and whether they can be applied to nondifferentiable nonconvex setting is not known. Indeed, our work appears to be the first paper that provides an FL method with complexity guarantees for solving bilevel optimization problems where the $\\textbf{lower-level problem may be constrained.}$ There have been several recent works that have highlighted the challenges in solving this type of hierarchical problems (i.e., Stackelberg games), even in centralized settings. For example, consider $\\min_{x \\in [-1,1]}\\ \\max_{y \\in [-1,1],\\ x+y\\leq 0}\\ x^2+y$. The solution is $(x^*,y^*)=(0.5,-0.5)$. The same problem, but with a reversed order of min and max, $\\max_{y \\in [-1,1]}\\ \\min_{x \\in [-1,1], \\ x+y\\leq 0}\\  x^2+y$, has the solution $(x^*,y^*)=(-1,1)$. One of our major contributions is that Algorithm 2 can be employed to address this challenging class of problems in FL. To elaborate, please see Remark 1 and Table 1 where we provide explicit communication complexity results for addressing bilevel FL  under use of different FL methods for the lower level problem. These are only a few instances of the breadth of FL problems that we can provably address by Algorithm 2."}, {"review_id": "m6C2N69m4s", "reviewer": "Reviewer_LNaU", "summary": "The paper considers the federated optimization problem with the non-smooth non-convex target function. The authors use a zero-order oracle, which allows to approximate the gradient. This approximation is related not only to the original target function, but also to its smoothed version (an additional theoretical object obtained using the random smoothing technique). For a new smooth target function, there are methods in the literature for solving it, and this is what the authors use. Mini-max problems and bilevel optimization are also considered. Experiments are given. ", "questions": "No", "limitations": "The paper is theoretical, therefore there is no need to discuss the social negative impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "For me, the article is nicely written and easy to follow.", "weaknesses": "I ask the authors to pay attention to this work:\n\nGasnikov, A., Novitskii, A., Novitskii, V., Abdukhakimov, F., Kamzolov, D., Beznosikov, A., ... & Gu, B. (2022). The power of first-order smooth optimization for black-box non-smooth problems. arXiv preprint arXiv:2201.12289.\n\nIt gives a more or less unified scheme of how by taking any practical first-order stochastic method for smooth problems to obtain a gradient-free method for non-smooth problems. It seems that using this scheme one can obtain the results of this paper as well. Moreover, this scheme is not new; it has been used for 10 years in most papers on gradient-free optimization.  In particular, the facts that are proven in the article under review are also used in the article I cited and there are links from where they are taken. \n\nPlease also note the refs within the article I cited. For example, there are references to works with gradient-free methods of solving saddle point problems. \n\nFinally, the contribution of this paper looks rather technical and at the moment I am not ready to accept the work. But perhaps the authors will change my mind in the process of rebuttal. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for bringing this paper to our attention. We will\ninclude this work in our references and comment on it in section 2. With respect, this paper has significant differences in scope and treatment with our work. We clarify these in the following.\n\n(i) First, note that this paper studies zeroth-order schemes for $\\textbf{nonsmooth convex}$ optimization problems, while we study $\\textbf{nonsmooth nonconvex}$ federated stochastic optimization problems. The progression from convex nonsmooth to nonconvex nonsmooth leads to significant challenges and necessitates the introduction of Clarke-stationarity. As we have noted in lines 144--147, our work in designing Algorithm 1 is motivated by recent findings where it is shown that for a subclass of nonsmooth nonconvex functions, computing an $\\epsilon$-stationary point is impossible in finite time. In Algorithm 1, we employ randomized smoothing to develop a zeroth-order FL method and then, in Proposition 1, we leverage a relationship between stationarity with respect to the smoothed problem and $\\eta$-Clarke stationarity. The result in Proposition 1 is complemented in Theorem 1 where we provide explicit performance guarantees for computing a stationary point to the smoothed problem. To our knowledge, these guarantees did not exist for nondifferentiable nonconvex FL.\n\n(ii) Second, the paper you mentioned does not address hierarchical optimization problems. However, one of the key contributions in our work is the design of Algorithm 2 and its complexity analysis in Theorem 2 for addressing hierarchical problems in FL. To highlight our contributions, consider the (centralized) bilevel minimization of $f(x,y(x))$ with respect to $x$ where $y(x) \\in \\hbox{arg}\\min_{y \\in \\mathcal{Y}(x)}\\ h(x,y)$. First, note that even when $f$ is smooth and convex in $(x,y)$, the implicit function $f(\\bullet,y(\\bullet))$ is often nondifferentiable nonconvex in $x$. Second, the analytical form of $y(\\bullet)$ is unavailable in most ML applications, such as hyperparameter ML. As such, $\\textbf{the zeroth-order information of the implicit function $f(\\bullet,y(\\bullet))$ is not available.}$ In view of this challenge, it is not clear how one can develop a provably convergent zeroth-order method for computing a stationary point to the nonsmooth nonconvex and hierarchical problem $\\min_{x}\\ f(x,y(x))$. A naive idea is to inexactly compute $y(x)$. However, an inexact computation of $y(x)$ leads to a bias in the zeroth-order information of $f$ and consequently, a bias in the approximation of its zeroth-order gradient. This $\\textbf{bias further propagates}$ throughout the implementation (please see Theorem 2(i) where we manage to derive the aggregated bias as $\\sum_{r=0}^R{\\varepsilon_r}$). Our work precisely addresses this challenge in Theorem 2. Importantly the bound in Theorem 2(i) implies that even when we inexactly compute $y(x)$ using a standard FL scheme, we are able to derive complexity guarantees for solving bilevel FL problems. \n\nPlease note that a major technical challenge we faced in designing Algorithm 2 is that $\\textbf{inexact evaluations of $y(x)$ must be avoided during the local steps.}$ This is because we consider bilevel problems where both the levels are distributed. Because of this, the inexact evaluation of $y(x)$ by each client in the local step in the upper level would require significant communications and is counter-intuitive to the nature of the FL framework. We carefully address this challenge by introducing delayed inexact computation of $y(x)$. Please see step 8 in Algorithm 2 and note how $y_{\\varepsilon}$ is evaluated at $\\hat x_r +v_{T_r}$ that is a different vector than the vector used by the client, i.e., $x_{i,k} +v_{T_r}$. At each communication round in the upper level, we only compute $y(x)$ inexactly twice in the global step and then use this $\\textbf{delayed information}$ in the local steps. $\\textbf{This delayed inexact computation of $y$ renders some technical challenges}$ in the proofs and so, we hope that the design and analysis of Algorithm 2 are not viewed as simple extensions of existing zeroth-order methods. \n\nLastly, we thank you for considering to reevaluate our work. Although our work may seem technical, we hope to clarify on the significance of the results in our paper and how they benefit the research on FL. Our work appears to be the first paper that provides an FL method with complexity guarantees for solving bilevel optimization problems where the $\\textbf{lower-level problem may be constrained.}$ There have been several recent works that have highlighted the challenges in solving this type of hierarchical problems (i.e., Stackelberg games), even in centralized settings. For example, consider $\\min_{x \\in [-1,1]}\\ \\max_{y \\in [-1,1],\\ x+y\\leq 0}\\ x^2+y$. The solution is $(x^*,y^*)=(0.5,-0.5)$. The same problem, but with a reversed order of min and max, $\\max_{y \\in [-1,1]}\\ \\min_{x \\in [-1,1], \\ x+y\\leq 0}\\  x^2+y$, has the solution $(x^*,y^*)=(-1,1)$. While we are unaware of zeroth-order methods for solving such problems even in centralized settings, one of the major contributions in our work is that Algorithm 2 can be employed to address this challenging class of problems complicated with the need for federated learning in both levels. Indeed, Algorithm 2 only requires solving the inner level problem for a fixed $x$ inexactly. In the case where the inner level problem is constrained, as it is the case in the above example as well as adversarial problems in FL, we may use a suitable method for solving the lower level problem for a fixed value of $x$ (see Algorithm 2, step 4). To provide more details on this, please see Remark 1 and Table 1 in our paper. We have provided explicit communication complexity results for addressing bilevel FL problems under use of different FL methods for the lower level problem. These are only a few instances of the breadth of FL problems that we can provably address using Algorithm 2."}, {"review_id": "gdvIA6goLx", "reviewer": "Reviewer_U9HM", "summary": "\nThe authors tackle the problem of nondifferentiable nonconvex locally constrained federated learning (Eq. $FL_{nn}$), and the bilevel variant (Eq. $FL_{bl}$). The minimax settings (Eq. $FL_{mm}$) is a special case of the latter. \n\nThe authors provide error, iteration and communication complexity for these settings where both non-convexity and non-differentiability is assumed.", "questions": "* Why is the final loss so big in Fig. 2? \n\n**Clarity.**\n\n* A reader not acquainted with Moreau smoothing cannot understand Eq. (1) without further research. Defining $\\mathbb B$ and $I_X^\\eta$ is advised (or at least point to `l. 158`). \n* Likewise, a reference for Eq. (4) is advised (or at least point to `l. 147`). \n* Lemma 1 in `l. 161`, Prop. 1 at `l. 171`, Thm. 1 at `l. 182`, Thm. 2 at `l. 209`: refer to the appendix' location of the proof. \n\n**Presentation.**\n\n* Tables 1 and 2 are useful summaries of the result. The font is however smaller than the rest of the text. \n* Framed environments `l. 48` and `l. 90` have italic or bold titles. Choose one of them?  \n* It is a matter of taste, but I would emphasize the text of Definition and Proposition environments so that they stand out of the main text.\n* Fig. 1 and 2 require bigger legends (or moved to the caption)\n* `l. 270`: `\\exp` instead of `exp` ", "limitations": "Discussing the significance of the results of Thm. 1 and 2 would be helpful.\n\nThe comparison with other FL scheme in Table 2 is done with different metric of accuracy. Relating those metrics would provide insight on the theoretical benefits of Alg. 1, and would complements the finding of the experiment section. Notably, highlighting the role of $\\eta$ in Table 2 and in Thm 1 and 2 would be welcomed too, as it is an important hyperparameter (complementary to the small remark `l. 263-265`). ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The reasoning for obtaining the algorithm is clearly explained in Sec. 1. \n\nThe experiment section is relevant and provides a clear comparison with other methods. ", "weaknesses": "Contrary to the reasoning for obtaining the algorithm, the results of Thm. 1 and 2 are not discussed. Doing so would help understand their significance. Typically, do lower bounds exist in some specific settings? What are the interpretation of the different terms? What are the dominant ones? \n\nOf lower importance, the reading is a bit complicated: the content is dense, with lots of technicalities and equation in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable suggestions and detailed comments on improving this work. Below, please see our response to each comment. \n\n$\\textbf{Your comment:}$ Contrary to the reasoning for obtaining the algorithm, the results of Thm. 1 and 2 are not discussed. Doing so would help understand their significance. Typically, do lower bounds exist in some specific settings? What are the interpretation of the different terms? What are the dominant ones?\n \n$\\textbf{Our response:}$ Your point is well-taken and we do agree that a remark on Theorem 1 would help with this clarification. Indeed, the communication complexity in Theorem 1, in terms of dependence on the number of clients denoted by $m$ and the parameter $\\epsilon$, matches with the existing complexities for addressing smooth nonconvex FL. Importantly, this implies that the use of randomized smoothing does not lead to a degradation of the main complexity bounds in terms of the smoothed problem. Please note that we mention the utility of Theorem 2 in Remark 1. We would like to note that our major contribution in this work lies in the design and analysis of Algorithm 2 in addressing hierarchical FL and so, we attempted to emphasize on this matter in Remark 1.\n\n$\\textbf{Your comment:}$ Of lower importance, the reading is a bit complicated: the content is dense, with lots of technicalities and equation in the main text.\n \n$\\textbf{Our response:}$  Thank you for raising this issue. We will add more intuition to the  technical details to ease the reading.\n\n$\\textbf{Your comment:}$ Why is the final loss so big in Fig. 2?\n \n$\\textbf{Our response:}$ We believe this is mainly because of the starting point we choose, we use vectors of all ones. \n \n\n$\\textbf{Your comment:}$ A reader not acquainted with Moreau smoothing cannot understand Eq. (1) without further research. Defining $\\mathbb B$ and $I_X^\\eta$ is advised (or at least point to l. 158). Likewise, a reference for Eq. (4) is advised (or at least point to l. 147). Lemma 1 in l. 161, Prop. 1 at l. 171, Thm. 1 at l. 182, Thm. 2 at l. 209: refer to the appendix' location of the proof.\n \n$\\textbf{Our response:}$ Thank you for your suggestions on making the paper more reader-friendly. We will address these by adding some intuitive explanation and point the location of our import lemmas and propositions.\n\n$\\textbf{Your comment:}$ Tables 1 and 2 are useful summaries of the result. The font is however smaller than the rest of the text. Framed environments l. 48 and l. 90 have italic or bold titles. Choose one of them? It is a matter of taste, but I would emphasize the text of Definition and Proposition environments so that they stand out of the main text. Fig. 1 and 2 require bigger legends (or moved to the caption). l. 270: $\\exp$ instead of exp.\n \n$\\textbf{Our response:}$ We agree with your helpful suggestions on the presentation of this paper. We will address these to make the important parts of this paper more clear and consistent.\n\n$\\textbf{Your comment:}$ Discussing the significance of the results of Thm. 1 and 2 would be helpful. \n \n$\\textbf{Our response:}$  Thank you for your suggestion. We may provide the following note to clarify the significance of the results in our paper and how they benefit the research on FL. \n\nThis work appears to be the first paper that provides an FL method with complexity guarantees for solving bilevel optimization problems where the $\\textbf{lower-level problem may be constrained.}$ There have been several recent works that have highlighted the challenges in solving this type of hierarchical problems (i.e., Stackelberg games), even in centralized settings. For example, consider $\\min_{x \\in [-1,1]}\\ \\max_{y \\in [-1,1],\\ x+y\\leq 0}\\ x^2+y$. The solution is $(x^*,y^*)=(0.5,-0.5)$. The same problem, but with a reversed order of min and max, $\\max_{y \\in [-1,1]}\\ \\min_{x \\in [-1,1], \\ x+y\\leq 0}\\  x^2+y$, has the solution $(x^*,y^*)=(-1,1)$. One of the major contributions in this work is that Algorithm 2 can be employed to address this challenging class of problems complicated with the need for federated learning in both levels. To provide more details on this, see Remark 1 and Table 1 where we have provided explicit communication complexity results for addressing bilevel FL problems under the use of suitable FL methods for the lower level problem with different assumptions. These are only a few instances of the breadth of FL problems that we can provably address using Algorithm 2.\n\n$\\textbf{Your comment:}$ The comparison with other FL scheme in Table 2 is done with different metric of accuracy. Relating those metrics would provide insight on the theoretical benefits of Alg. 1, and would complements the finding of the experiment section. Notably, highlighting the role of $\\eta$ in Table 2 and in Thm 1 and 2 would be welcomed too, as it is an important hyperparameter (complementary to the small remark l. 263-265).\n \n$\\textbf{Our response:}$ Thank you for this important observation. We would like to note that naturally, in view of Lemma 1(iv), the dependence on $\\eta$ would be similar to the dependence on inverse of the Lipschitzian parameter in smooth nonconvex FL. However, we can add the dependence on $\\eta$ in the convergence rate in Thm. 1 and 2, as the random variable $v$ for zeroth-order method depends on it. As we have shown explicitly in Thm. 1 and 2, the rate depends on $\\eta$ and we also validated this in our experiment in sec. 5.1. "}]

Author rebuttal:
We sincerely appreciate all the reviewers for their time and thoughtful reviews on improving this paper. The following is a summary of major changes that would appear in the revision if accepted. 

1. In response to reviewer "Lumm" and "LNaU", we will add the following note to emphasize the significance of our contributions in addressing bilevel FL problems.

This work appears to be the first paper that provides an FL method with complexity guarantees for solving bilevel optimization problems where the $\textbf{lower-level problem may be constrained.}$ There have been several recent works that have highlighted the challenges in solving this type of hierarchical problems (i.e., Stackelberg games), even in centralized settings. For example, consider $\min_{x \in [-1,1]}\ \max_{y \in [-1,1],\ x+y\leq 0}\ x^2+y$. The solution is $(x^*,y^*)=(0.5,-0.5)$. The same problem, but with a reversed order of min and max, $\max_{y \in [-1,1]}\ \min_{x \in [-1,1], \ x+y\leq 0}\  x^2+y$, has the solution $(x^*,y^*)=(-1,1)$. One of the major contributions in this work is that Algorithm 2 can be employed to address this challenging class of problems complicated with the need for federated learning in both levels. To provide more details on this, see Remark 1 and Table 1 where we have provided explicit communication complexity results for addressing bilevel FL problems under the use of suitable FL methods for the lower level problem with different assumptions. These are only a few instances of the breadth of hierarchical FL problems that we can provably address using Algorithm 2.

2. In response to reviewer "Lumm", "CtdY" and "U9HM", we will add more interpretation of technical terms to smooth reader's experience, such as a note on the bounded set dissimilarity (eq. 3) that is an instance of the "bounded gradient dissimilarity" condition, and we will present the definition of Clarke stationary point earlier in section 1. 

3. In response to reviewer "Lumm", "CtdY" and "LNaU", we will add a paragraph to discuss and compare other zeroth-order methods in FL  and emphasize that they have made stronger assumptions than in our work.

4. In response to reviewer "CtdY" and "U9HM", we will provide all the complexity results explicitly in terms of both problem dimension $n$ and smoothing parameter $\eta$. 

5. In response to reviewer "CtdY", we will apply our method on other datasets such as Cifar-10.

6. In response to reviewer "U9HM", we will add a note to discuss the significance of Thm. 1 and Thm. 2.

Please see the $\textbf{detailed responses}$ to the reviewers.

Meta-review: The paper considers the federated optimization problem with the non-smooth non-convex target function. In general, the reviewers are not against the acceptance of this paper. However, they pointed out that the authors need to carefully take their suggestions and incorporate the discussions into the final version. For example, the reviewer found the contribution of Section 4 interesting and would advise the authors to emphasize Section 4 in terms of experimentation. Please consider all the suggestions in the detailed reviews and from the discussions with the reviewers.
Decision: Accept (poster)