How Does Black-Box Impact the Learning Guarantee of Stochastic Compositional Optimization?
Authors: Jun Chen
Hong Chen
Bin Gu
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic compositional optimization
theoretical guarantee; black-box optimization; stability analysis
Primary area: learning_theory

Abstract: Stochastic compositional optimization (SCO) problem constitutes a class of optimization problems characterized by the objective function with a compositional form, including the tasks with known derivatives, such as AUC maximization, and the derivative-free tasks exemplified by black-box vertical federated learning (VFL). From the learning theory perspective, the learning guarantees of SCO algorithms with known derivatives have been studied in the literature. However, the potential impacts of the derivative-free setting on the learning guarantees of SCO remains unclear and merits further investigation. This paper aims to reveal the impacts by developing a theoretical analysis for two derivative-free algorithms, black-box SCGD and SCSC. Specifically, we first provide the sharper generalization upper bounds of convex SCGD and SCSC based on a new stability analysis framework more effective than prior work under some milder conditions, which is further developed to the non-convex case using the almost co-coercivity property of smooth function. Then, we derive the learning guarantees of three black-box variants of non-convex SCGD and SCSC with additional optimization analysis. Comparing these results, we theoretically uncover the impacts that a better gradient estimation brings a tighter learning guarantee and a larger proportion of unknown gradients may lead to a stronger dependence on the gradient estimation quality. Finally, our analysis is applied to two SCO algorithms, FOO-based vertical VFL and VFL-CZOFO, to build the first learning guarantees for VFL that align with the findings of SCGD and SCSC.

How Does Black-Box Impact the Learning Guarantee of Stochastic Compositional Optimization?
Jun Chen
College of Informatics, Huazhong Agricultural University, China cj8504872430163.comm
Hong Chen'
College of Informatics, Huazhong Agricultural University, China Engineering Research Center of Intelligent Technology for Agriculture, China chenh@mail 1. hzau. edu.
Bin Gu
School of Artificial Intelligence, Jilin University, China Mohamed bin Zayed University of Artificial Intelligence j jsgubinegmail. com
Abstract
Stochastic compositional optimization (SCO) problem constitutes class of opti- mization problems characterized by the objective function with a compositional form, including the tasks with known derivatives, such as AUC maximization, and the derivative-free tasks exemplified by black-box vertical federated learning (VFL). From the learning theory perspective, the learning guarantees of SCO algo- rithms with known derivatives have been studied in the literature. However, the potential impacts of the derivative-free setting on the learning guarantees of SCO remains unclear and merits further investigation. This paper aims to reveal the impacts by developing theoretical analysis for two derivative-free algorithms, black-box SCGD and SCSC. Specifically, we first provide the sharper generaliza- tion upper bounds of convex SCGD and SCSC based on a new stability analysis framework more effective than prior work under some milder conditions, which is further developed to the non-convex case using the almost co-coercivity property of smooth function. Then, we derive the learning guarantees of three black-bol variants of non-convex SCGD and SCSC with additional optimization analysis. Comparing these results, we theoretically uncover the impacts that a better gradient estimation brings a tighter learning guarantee and larger proportion of unknown gradients may lead to stronger dependence on the gradient estimation quality. Finally, our analysis applied to two SCO algorithms, FOO-based vertical VFL and VFL-CZOFO, build the first learning guarantees for VFL that align with the findings SCGD and SCSC.
Introduction
In recent years, stochastic compositional optimization (SCO), class of optimization methods that incorporate the compositional form ([((w)), ,, has garnered significant attention in the research
Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

community 12
3
4
5
6
77 It represents a special case of stochastic bilevel optimization g
min w WEWER"
Eg [fa (ur, o (w))) s.t. "" (1=) = arg min E.g [M=(w,,,) w)],
1ESt
where [x[:] represents the expectation with respect to (w.r.t)) the sample 2, parameters w E W E R? and v E Rd. If the inner function (w, v) = ||v - (w))l and the outer function f is only function of U, i.e., [=(w, v) = [=)),, the stochastic bilevel optimization reduces to the SCO:
min WEWER
{F(w)= f(((w) = E3g (E, [od(w)))
(2)
where F(w) is the compositional population risk, f RRd + IR. g R2 + RR. f(v) Eg [Jz(v) and g(w) = F2 [-= (w)).
Many applications adhere to the form of SCO 2 such as risk averse optimization group
distributionally robust optimization [10], AUC maximization [1 13 [1], model-agnostic meta- learning (15), and tisst-odde-optimizztion baaiion---ddddd vertical federated learning (FOO-based VFL) [16]. Apart from the above applications with available derivatives, there exist derivative-free scenarios as well, such as reinforcement learning [17] and zeroth- wwt--ooorttiizzzattiiei based E2OO-based VFL [18 [1]. [2 discussed the extension of stochastic compositional gradient descent (SCGD) to the derivative-free setting, called black-box SCGD, where the zeroth-order information of f or g is available through sampling-
From the perspective of statistical learning theory 20), the theoretical guarantees pertaining to generalization and optimization performance for SCO algorithms are worth studying to validate their empirical behaviors. The former assesses the disparity between the empirical performance and the population performance for the trained model. The latter measures the empirical performance gap between the trained model and the empirical optimal model. To our knowledge, there is only one study attempting to provide a generalization guarantee in this area. 21 has pioneered the generalization understanding of two notable SCO algorithms, i.e., SCGD and SCSC [5] via algorithmic stability tool. They have achieved satisfactory excess risk bounds by selecting some specific values of T to balance stability results and optimization errors. However, the intricacy of their analysis framework brings some unnecessary terms in their results leading to these large T values that it is practically challenging to complete these iterations within a reasonable timeframe. Furthermore, the study has yet consider more practical scenario beyond convex and strongly convex cases, specifically, the non-convex case. For the optimization guarantee, plenty of work devotes to studying the convergence behaviors of some first-order SCO algorithms 2 3 and their extensions (22 23 24 25 For
example, 2 proved that SCGD can converge almost surely to an existing optimal solution with the rate O (T-1/4) for non-smooth convex problems and the rate O (T-2/7) for smooth convex problems, where T is the total number of iterations. (5) presented that stochastically corrected stochastic compositional gradient method (SCSC) can achieve the same convergence rate O (T-1 as SGD for non-componn conpooompoiii problems. However, there exists a research gap in the optimization analysis for the derivative-fres free SCO algorithm as well as in its generalization analysis.
Considering these problems, this paper leverages algorithmic stability to obtain some similar and even superior results of SCGD and SCSC under the milder parameter selection and the non-convex condition. More importantly, to apply a broader class of stochastic optimization problems, this paper pioneers the theoretical analysis of the black-box SCO algorithms, which uncovers the impacts of black-box on the learning guarantees of SCO algorithms. Our main contributions are listed as follows.
Generalization guarantees under some milder settings. Firstly, we provide the sharper generalization upper bounds of convex SCGD and SCSC based on a new stability analysis framework more effective than prior work [21] with more practical selection T'. Subse- quently, we develop the above convex analysis to the non-convex case by introducing the almost co-eoricvvtty property of smooth function, which yields satisfactory generalization guatee
guarantees of SCGD and SCSC under the non-convex condition.
Learning guarantees for black-box SCO algorithms. To apply a broader class of stochastic optimization problems, we further consider three black-box variants (outer, inner, and full black-box) of SCGD and SCSC to obtain the generalization and optimization upper bounds similar to the ones of SCGD and SCSC. Comparing the first-order and zeroth-order results, several key insights into the impacts of black-box on the learning guarantees of SCO algorithms are shown: 1) closer estimation distance brings better result; 2) more

---

estimation directions lead to a better result: 3) larger proportion of unknown gradients results stronger dependence on the gradient estimation quality.
Applications VFL. Finally, explore the applications of our analysis framework to two specific SCO algorithms, i.c., FOO-based VFL and VEL-CZOFO, where we build the pioneering stability-basee generalization and optimization guarantees for first-order and zeroth-order VFI. algorithms that align with the findings of SCGD and SCSC.
Preliminaries
This section describes the learning paradigm of SCO and introduces two popular SCO algorithms (SCGD and SCSC) and their black-box variants in detail at first. Then, some necessary definitions and assumptions are provided for our theoretical analysis. The explanations for all symbols shown in Table 3 located in Appendix A
Considering stochastic compositional optimization algorithm (2. the distributions of sample and are unknown. The training dataset = 5* US$ {=1.... Zn. ( ..... 2m
available obtain
the final output model parameter A(S) via minimizing the following compositional empirical risk
Fs(w) = fs(gs(w))
1
Σ
m
fey
Σ n
9z, (w)
m
==1
(w). fs(v) = 1 Σド fz, (v), 21.... 2n. ...... 7m are independent. where gs(w) = +. lt, Besides, we denote by w(S), w" the empirical optimal model parameter on and the global op- timal model parameter, defined as w(S) arg min Fs(w) and w" arg min F(w). Then, the wEW
wEW generalization error, optimization error and excess risk of A(S) are given by [F(((S) ((A(S))Fs(AAS)) Fs(A(S)) (w() and F(A(S)) F(w*). respectively. Since B[F(A(S)) FF("))) 2 0 and (wFs(w(()) F(w")] < O, the excess risk of ASS) can be decomposed as the summation of generalization error and optimization error follows
[[F(((()) F(w")] [[[F(((S)) Fs(A(S)) + Fs(w((S))
(3)
where [0]-] denotes the expectation w.r.t. all randomness.
In this work, we primarily investigate the learning guarantees of two prevalent SCO algorithms, i.e., SCGD (2) and SCSC [5], along with their black-box variants. Algorithm presents the detailed parameter update procedures of these algorithms. The difference between SCGD and SCSC lies in the update of the outer model parameter vt. For SCGD, ut+11 is the linear combination of e and 9z, (wx). However, this update may lead to a suboptimal convergence rate when the learning rate 3 of the outer model update is smaller than the learning rate 1/1 utilized for the inner model update. To alleviate this problem, SCSC updates u++1 with the combination of the "corrected"
and 9s., (wz). where or is corrected by 9s. (w;)= 9s., (we-1) so that U++1 approximates 9a., (w;) (5). Besides, [2) discussed the extension of SCGD the derivative-free setting where only the zeroth-order information of g is available through sampling, which potentially applies to broader class of stochastic optimization problems. Here, we show the first-order gradient estimation of f. which is similar that of g. The unknown first-order gradient of f is estimated by Equation and then approximated by Taylor expansion (5) in our analysis
VJs, (1+41)
Wrl1 (Jzj, (Ue41 + pmu,)) - SEy, (v++1))
(4)
b
1=1
(V,,,, (ve+1), una) ue + ( (H( T fz, (V)le=vi,, ve.))
(5)
where (ur,)) - is the set of independent and identically distributed (i.id.)) random direction vectors (obeying the d-dimensional uniform distribution), and is the distance between two model parameters (Ve+1 + u and 12+1) used to estimate the gradient in the /-th direction.
Drawing inspiration from the classical non-compositional stability analysis work 26 and the pio- neering work 21 investigating the generalization of SCO, we introduce the definition of uniform model stability as follows.

---

Algorithm 1 (Black-box) SCGD/ / SCSC
Require: 81, W1: initial outer model and inner models; B, m) initial learning rates
for all t t= 1,.., 7 do
Randomly sample E [n]. obtain Izz, (we) and Vgs,, (xex) (Inner black-box: obtain Va (w))
similar to Equation (4)
SCGD: Update ut+1 = (1 - B) + 8gz., (we)
SCSC: Update Ut+1 = (1 11--)) 8)v, + Bga., (wy) + - (1,, (we) - ge., (w:-1))
Randomly sample Je [mm], obtain fzz, (ut+1) (Outer black-box: obtain V fz, (U(+1))
Update Wh+1 = Wt 9 (w/) V VJz,, (U++1)/ /We+1 = We - 7 Vgz., (wor V fz, (1(+1)
/we+1 W02 ?) V 9.., (we) fa (ve+1 W641 we 1/ V (w)) V fa,, (12+1)
end for
Ensure: Final model wr
Definition 1. The randomized algorithm A for SCO problem is uniformly model (Ez, e2) if
AA [|) A(S <:z and EA [l])(S) - A(S S 62,
where || || is the Euclidean distance || |l2 and 8 = {21, ... Zng 21 =m S {21, ... 2/-1 24. 24+1, ... Zng 31, ... 2m S... (21,.. Zno 31, ... 2z-1, Ky 2j+1, 3m for any i [m],j E [m].
According to the foundational concept of algorithmic stability, Definition I considers the two datasets obtained from the perturbation of a single sample in { and { y= respectively, where the altered sample 2 is i.i.d. to 23. and so does zy. Prior to filling the relationship gap between the uniformly model stability and the generalization error E [{((())) Fs( (A it is essential to make some fundamental assumptions, i.e., Lipschitz continuity (bounded first-order gradient) of f and bounded variance of g.
Assumption 1. For any parameters w, w W, of E RRd and some Lgs L 0, functions 92 (w) and fv( are Lipschitz continuous, Lee, || [ (w) S Ly and [f(w))] < L,g, which also mean that (w) 9= (=(w))l I Ly ||l w/|l and [f=(c) - fz(t')) S Lg V.
In numerous compositional 2 5 and non non-compositional studies 26 27 Assumption I serves
general theoretical bridge analyzing the generalization and optimization performance.
Assumption 2. For any E W and some Vg > 0, the variance of function 9=(w) is upper bounded by Vg.. i.e., Ex [19)(w) - - <
The bounded variance is also a classical condition for statistical learning theory 2 3, 6 7 28 29 30 which limits the ranges of the variance value of the given functions Utilizing these two fundamental assumptions, Theorem builds a rigorous relationship between stability and generalization error, thereby enabling stability to measure the generalization performance in the subsequent analysis. Note that, Theorem was previously proved by (2 (Theorem 2.3), so we omit its detailed proof here for brevity.
Theorem 1. (27) Let Assumptions 2 hold. Assume the randomized algorithms A for SCO problem uniformly model (s)stalee then,
((A(() - -Fs(A(S)) < LgL,((cc + 1 +
Remark 1. As mentioned in (21y. Theorem iis the compositional counterpart of Theorem 2.2 in 126). In other words, the above result is equivalent to (A()) Fs((()) S Lffg when g=(w) w. i.e. F(w)= Ez [f>(w)) and Fs (w) no - (w). If the order of eg is faster than O ((2+n-t) the generalization upper bound of SCO algorithm will be primarily constrained by the term ALgLfEe +Lyvn-Vy attributed to the compositional structure. Otherwise, there is little difference between Theorem ] and Theorem 2.2 (26).
The subsequent assumptions and definition required by the stability analysis in Section

---

Assumption 3. For any parameters w' E w. (u) and fa (w)) are smooth, i.e, ge - og. [ ay and ( a, which also mean that
v. o' R² and some ag. a. > 0, functions (w).
[V) (gz(w')ll og - [V//(()) V52(201 5
and
[Vfs(o:(w)) fs(ao(w())) S || w'll
Definition 2. For any parameter v, E IRd, function f Rd + IR is convex if f(v) 2 f(v)) (VS()'), -²)-
Assumption 4. For any E W R., direction vector u. step size μ 0 and some Mg, M,, Ma M > O, the following inequalities hold
11 + pm)) g=(w)]l S Mg. Isz(U + +u) [=(w)] MG,
and
Vg= + pm) Vg=(w)ll S My [Vfa(t+ V S
Remark 2. Assumption 3 the most important condition for our analysis since there are several key properties (Lemma 4 of smoothness required to measure the algorithmic stability. In addition, our stability analysis framework relies crucially on another key lemma (called co-coercive lemma, Lemma [ derived from the smoothness and convexity of the function f(w). Therefore, we provide the definition of convexity Definition 2 Except for the convex case (Section 3.D. this work mainly considers some non-convex cases (Sections 3.7 3.2p. Although the co-coercive lemma is not available without the convexity condition, a surrogate lemma (called almost co-coercive lemma, Lemma takes similar role within our analysis framework. Finally, Assumption 4 Agives the upper bounds of the difference between two adjacent function values for 9, J, Vg, J., which represents less stringent assumption compared to the general bounded condition [26]. Specifically, Assumption A different from the assumption If[ I M. Assumption 4 requires the distance between two adjacent function outputs to be bounded, i.e., 11g( w (uu) g g(w)ll S My. If(u pu) f(v)] < M,, which milder than Ifl I M. Besides, also requires the distance between two adjacent gradient outputs to be bounded, i.e.. [/Vg(w + pu) Vg(w)]l < M || f( + pu) V f(v)ll S M', which is
milder than bounded gradient condition | < L 126)
3
Main Results
This section presents the learning guarantees of two SCO algorithms (SCGD and SCSC) under several cases. The comparisons among our results and previous work are summarized in Tables ] 2 and their proofs are provided in Appendices C D
3.1 Learning Guarantees for General SCO
Firstly, we consider the generalization analysis for the general convex SCO algorithm.
Theorem 2. Let Assumptions hold and the function [g(w)) is corvex. Assume that the randomized algorithms A (Algorithm 1 for SCO problem brings the model sequences {w; W and
2.2 T
(fwe) J-m1)
T
on S and Si.= (53.5) with the step size sequence {T=)T=
28 the final output A(S) wr is uniformly model (Ez, -s)-bll with (a) For SCGD with ni 't'
1LgL,Blog(eTT and Eg
4LyL,8 log(eT))
e,
an
am
(b) For SCSC with nh
a the final outpul A(S) wr is uniformly model (Ez, -stble with
4L log(eTT) and Eg
4LyLg log(e'T))
c,
an
am
5

---

Table 1: Comparisons among the stability-based generalization guarantees for SCO algorithms and SGD (Thm.-Theorem; Cor-Corollary; x-high probability bound; L, a, V, V.,,Cc--iipshitz continuity, smoothness, bounded variance, bounded function, and convexity assumptions; c-a positive constant; V-has such a property; x-hasn't 't such property).
Assumptions
Algorithm
Generalization
L
a
V
M
C.
SGD
26
Thm. 3.8)
0 (n log T)
V
YY
X
V
SGD B1
Thm. 4)
+0 ((
n2 [
T + n - log
V
J
V
SCGD/SCSC
O
T
(n + 1) T m
V
([2) Thm. 3.7) SCGD/SCSC
nn
+ m= log T' + n
(Thm.
SGD ([26)
Thm. 3.12)
0 nn T ..F1
SGD 32
Thm. 15)
0 n T OETT
SGD 60
Thm. 1)
0 (n log
SGD Cor. 17)
0 (n (T)
X
X
SCGD/SCSC
O 0(n + m 1) T log T + +n+ n
V
v
(Thm. 3
Cor.
VFI. (Cor.
O n 1T's log
V
v
x
Remark 3. Based on a new stability analysis framework more effective than prior work 12/V, Theorem states the stability upper bounds O (In+++m=)) 3 T) for SCGD and O ((n + m log T) for SCSC under the corvex condition, which derives a generalization bound O 0nn + m -1) log + - by combining with Theorem
Previously, (271 provided the sta- bility results (ril' (n + m 1) + 17 (T + + 3 + + for SCGD and o (1T (n + 1) + (T + 3 - + + 3 t for SCSC in the same setting,
where > 0 is an arbitrary constant. They selected = 0 o00orrrre 9) B = =o oo
2,
T = O (max m² m²)) for SCGD and nj = o ( 8 o o c > T
O max (ni.m²) m2]) for SCSC to yield the bounds O (max {n m 1) max n2, m }} which
is slight larger than O + Compared with 12V. Theorem enjoys not only tighter bounds but also some more practical parameter selections of 1), 3, T. There are some experiments
2 5 35 to validate this statement. (1) For T: [21] provided some generalization bounds for convex SCGD and SCSC with some impractical T such as T = O(max(n' /2 mmm2)) in Theorem 4. While our convex result (Theorem 2) can achieve similar rates even taking T (max (n, m)) which better matches some empirical observations (Fig. 1, 2 in (5) and Fig. in (21). (2) For n. Theorem
4 in (27) took 1): = -6/6 which is too small when T large. While Theorem 2 takes T): = O(1-1)
[4 35 ). (3) For closer to some empirical selections (1): 3/44 in 5 and πi- = 0(t
3e Theorem 4 in (2I] took 3, 4-/7 which is also too small since [2] 35y empirically select
B. = 1-12 or Br = 1-1 In contrast, Theorem 2 have special restriction on 3r.
Moreover, the bounds of Theorem 2 are similar some popular stability bounds in the non- compositional literature. For example, the most classical work (26] achieved the uniform sta- bility bound O (n logT)) for convex SGD with ne S 50 (t-1. [31] showed the uniform stability
I 2 + n 1 /lo((188) for convex pairwise SGD with t) O (T~)). The proof of
bound 0
Theorem 2 is provided in Appendix C

---

To further weaken our assumptions, the generalization analysis of the convex SCO algorithm is developed into the non-convex setting by introducing the almost co-coercivity property of smooth function.
Theorem 3. Let Assumptions I hold. Assume that the randomized algorithms A (Algorithm m 3.2
for SCO problem brings the model sequences {we)t=1 and { w t==1 ({
S and St.² (55.5) with the step size sequence {nt For SCGD with T S 2pt = 0g B + 3
and SCSC with ne S 2pt agll + L.a,, the final output A(S) wr uniformly model
(cz, -ttabe with
L ( log(cT) and L (eT) log(eT)
pn
pm
Remark 4. Under the non-convex setting, Theorem elucidates satisfactory stability bound O ((n''+ + log T but -timess larger than Theorem When T O (max m)) and ignoring logarithmic terms, this bound is equivalent to O max (n- mm max {nz, , m }). Therefore, under the further weakening condition, i.e., non-convexity, Theorem aacriveess the stability results similar to the ones of the convex SCGD and SCSC in (27V and some non-com compositional, non-convex results (26 30 33). The proof of Theorem is provided Appendix C
3.2 Learning Guarantees for Black-box SCO
The aforementioned results lay the groundwork for elucidating the impacts of black-box on the learning guarantees for the non-convex SCGD and SCSC, including additional optimization analysis. Three black-box cases shown in Algorithm [ are considered in this part. Prior to the analysis, we provide the following assumption required by the optimization analysis.
Table 2: Comparisons among the optimization guarantees for SCO algorithms (Thm--Theorem; Cor.-Corollary L, V. C.-isshii continuity, smoothness, bounded variance, bounded function, and convexity assumptions; d2 O(d); y-has such a property; x-hasn't 't such a property).
Assumptions
Algorithm
Optimization
&
M
C.
SCGD (2 Thm. 8)
0
T
SCSC 5 Thm. 1)
0 T
V
X
X
SCGD/SCSC (1 Thm. 3.7)
(
J
V
V
Outer black-box SCGD/SCSC (Thm.
0 0p2 4)
V
V
Inner black-box box SCGD/SCSC (Cor.
O (p
V
V
V
x
Full black-box SCGD/SCSC (Cor.
(nt 1 +
V
VFL-CZOFO (Ours, Cor. 5
O (4² 1 4)
V
x
Assumption 5. For any W and parameter
0, the empirical risk Fs(w) satisfies
E [|VVF(())][]]] > 2- [Fs(w) - Fs(w(S))).
In the absence of the convexity assumption, the gradient of empirical risk F[>)( = does not guarantee global optimal parameter. Assumption postulatss that all empirical local optimal parameters are, in fact, empirical global optimal parameters, which prepares for the characterization of (A(S)) Fs(w(S))].
Theorem 4. Let Assumptions
5 hold. Assume that the randomized algorithms A (Al- 7
gorithm I for SCO problem brings the model sequences {wi}rr and { w I t=1 ({ (fw) )
on S and Sh.* (S1.2) with the step size sequence {nelT= For the outer black-box SCGD with
7

---

22 2(a, (4 My
71 me P 2 max
and the outer black-box SCSC with nt my mxx 2
max/ (120
2((gMM)tliMM)) 2/ 7. M4y
J. the final output A(S) = urr has the learning guarantee
B[F(Wr) FFen))FF(WW0
F(w")) )1 S 50( ( (n
+ +m 1) ') log T + + +1² + 1 4b)))))
where d2 d - (2p + 1)33 + (p 2)²² 3² for SCGD and d2 = d 2 2p 1 + (p+ 2)²² for SCSC.
The proof of Theorem is provided in Appendix D
Remark 5. Theorem 4 considers the outer balck-box SCGD and SCSC algorithms where only the gradient of the outer function S is unknown.
establishes the excess risk 21 derived the excess risk bound bound O (nn + +m= T log T + n &/2 + 1² 12 bb) d2).
O (max {n- -1, ,mm max n2 m2 m2²)) for the convex SCGD and SCSC with the parameter selec- tions in Remark 3 Theorem can derive this bound with the milder condition T O (max m]) and T/2- = O 0(( (1-
For the generalization bound, Theorem 4 is consistent with Theorem 3 As for the optimization bound,
[2] proved the convergence rule B(IIF((WT) S O (T-*) SCGD for non-convex problems.
5 proved the convergence rate T E BIIVF( S SO ( of SCSC for non-convex problems. Compared with 5), Theorem 4 obtains the Alack-box-relac bound O (n²² + b- with some smaller learning rates required by our analytical framework. This bound is composed of two dependencies on the estimation distance μ and the number b of estimation directions in Equation (4). which shows the following two key insights into the impacts of black-box on the learning guarantees of SCO algorithms. Firstly, a small μ indicates a small distance between the two function values fv + pul and fv selected make gradient estimation f in the direction of the unit vector u. Therefore, a smaller p., i.e., a closer estimation distance, brings a better gradient estimation, resulting in a better excess risk bound. Secondly, a large b indicates that plenty of unit vectors u1, 1,....b b with different directions are selected make gradient estimation V {z())- Then, a larger b, i.e., more estimation directions, leads to a better gradient estimation, resulting in better excess risk bound. In summary, the bound of Theorem 4 verifies the fact that a better gradient estimation brings tighter learning guarantee for the outer black-box SCGD and SCSC.
Except for the tlac-bbox-related term, Theorem 4 chooses the learning rates affected by μ.. which is also different from Theorem 4 Although μ can be very small such as 10-4 4 [19,, its negative impact on qe can be eliminated by M, M' since the two inequalities M2/ /P S L and M S ay hold.
The inner black-box and the full black-box SCO algorithms are studied in the following two corollar- ies, respectively.
Corollary 1.
Let the assumptions of Theorem 4 hold. For the inner black-box SCGD with n/
{v20 2n
2(3Lyay M M,L,) and the inner black-box SCSC with T/. = p.t >
P P Z max
2 ML
max
(v
20
the final output A(S) = -TT has the learning guarantee g
14y
[[ - F(w")) 500
+ m (n-
T log T + - + 12+ bb
where d2 d - (2p 1)33 + (p+ 1)² 32 for SCGD and d2 = d 2p + (p+ + 1)² for SCSC. Corollary 2. Let the assumptions of Theorem 4 hold. For the full black-box SCGD with Ttt
PyLo P 2 max (Vze M,L,
and the full black- box SCSC with ny prt 2
1
max { /Var
2a 7,
ML the final outpus A(S) = -w has the learning guarantee
}.
E [F(wr) - F(w*)) 5 10 =0(00=0)''000 +m m1m T log T + - + 1²t + +b 2 + dzz
((ln))FF(w))))
8

---

where d2 = = 2 2) 2+ (p+ 2) B for SCGD and d2 = - 22 2) +p+ for SCSC.
The proofs of Corollaries 1 are provided in Appendix D
Remark 6. Corollary 0 provides the excess risk bound with the same order as Theorem 4 for the inner black-box SCGD and SCSC. The excess risk bound for the full black-box SCGD and SCSC in Corollary 2 presents the different dependencies on i and b. i.e., 11º + b- These dependencies also comply with the two key insights uncovered by Theorem| Corollary Besides, when p²b > d2 or 1²b < d2 holds, the term is dominated by nº² or b- which denotes a stronger dependence on the gradient estimation quality. Hence, Corollary shows that larger proportion of unknown gradients may lead a stronger dependence on the grudient estimation quality.
Applications
Considering the existing derivative- free cases in VFL, the analysis framework of SCGD and SCSC is herein applied to two VFL. algorithms, FOO-based VFL. [16] and VFL-CZOFO 19 As outlined in Algorithm of Appendix FOO-based VFL algorithm comprises two components, the K local clients with the model parameters w E [K] and the central server with the global model u. Concerning the data privacy, different clients do not communicate with each other directly, but exchange information indirectly through a server. For this reason, the objective function of the k-th client adopts the same compositional structure f (g (w*)) as SCGD and SCSC, To further ensure data privacy without additional protection techniques, VFL-CZOFO is proposed by introducing the idea of ZOO. Different from the general ZOO-based VFL [18], VFL-CZOFO employs zeroth-order gradient on the output layer of every client, with other parts utilizing the first-order gradient, which preserves the privacy protection of ZOO while significantly enhancing convergence.
Before stating our remaining results, it should be noted that there are few differences between the setting of FOO-based VFI. (VFL.-ZZOF) and the one of SCGD (SCSC). First of all, we set {.1,..., 21 24,, 21-1; .... En according to the learning paradigm of VFL. Therefore, Theorem is simplified Corollary 3 Secondly, the update of the outer model (global model) for FOO-based VFL WVFLCZZOFO is not based on the simple moving average in SCGD (SCSC). Thirdly, Assumptions
= (=1,...,2,) and $ 2
5 hold for every client in all K clients. Without loss of generality, we only study the learning guarantees of P0O-based VFL and VFL-CZOFO for the k-th client.
Corollary 3.
Let Assumption 7 hold. Assume the randomized VFL algorithms is uniformly model c stable, then, E[[F(A(S) - Fs(A(S))) s Ly
Corollary B gives the relationship between uniform model stability and generalization error under the setting of VFL. The proof of Corollary is omitted since it can be proved by Equation (15) in the proof of Theorem 2.3 (2 without the decomposition in Equation (14). The last two results study the theoretical performance of FOO-based VFL and VFL-CZOFO.
I 3 hold. For the k-th client (k E [K], assume that the randomized FOO-based VFI. algorithu (Algorithm brings the model sequences {w?] J Jzm1 and
Corollary 4. Let Assumptions
{ k.2,kk "w St-1 on S and S with the step size sequence (no S t0 aggs و + Lzay. Then, the final output A(S) = w of the k-th client has the generalization guarantee
I [[[(w)))sssuucd
-
(ll < 5 (0 (n- log logT).
Corollary Let Assumptions
3 hold. For the kithh client (k E [K]), assume that the random-
T and { ba,k T
J t== on S and S with the step size sequence (n (no) n) P max 2a My
ized VFL-CZOFO algorithm (Algorithm 2 brings the model sequences [w:)]
Then, the final output A(S) w of the kith client has the generalization guarantee
F (w F(w**)]] s O
17 log T + p²² 2= + b bd12))
where d2 =d o 2p 1 1 (p+ 1)

---

The proofs of Corollaries 5 are provided in Appendix E
Remark 7. Corollaries
5 both provide the first stability based generalization bound O On-ITz log T As for the optimization bound, Corollary gives O (n² + +2) which origi- nates from the outer black-box setting.
Apart from VFL, the generalization guarantee of zeroth-order horizontal federated learning (HFL) was studied with the algorithmic stability tool. [36] established the systematic theoretical assessments of synchronous federated zeroth-order optimization (FedZO) by developing the on on-average model stability analysis. Its generalizution bounds and optimization bounds all depend on the two gradient estimation-based parumeters p and b. From our perspective, the complicated compositional structure may be key factor that makes the generalization bound in Corollary 5 unaffected by the impact of the estimated gradient quality. The reason that the analysis framework of Theorem (36] requires decomposition (Equation (6)) which is hardly achieved due to the compositional structure in our analysis.
5 Conclusions
In this paper, we provide a novel, more effective theoretical analysis of two SCO algorithms, SCGD and SCSC, and their black-box variants utilizing the uniform model stability tool. The analysis framework is applied to the two VFL algorithms, FOO-based VFL and VFL-CZOFO. Our results not only offer satisfactory learning guarantees but also theoretically validate the impacts of black-box that a better gradient estimation brings a tighter learning guarantee and a larger proportion of unknown gradients leads to stronger dependence the gradient estimation quality. We hope our study can facilitate future theoretical analyses of SCO problems and inspire new practical algorithms.
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China (Nos. 12071 166 and 62376104) and the Fundamental Research Funds for the Central Universities of China (No. 2662023LXPY005).
References
[1] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1- 2):267-305, 2016
[2] Mengdi Wang, Ethan X. Fang, and Han Liu. Stochastic compositional gradient descent: algo- rithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2):419
2017.
[3] Mengdi Wang, Ji Liu, and Ethan X. Fang. Accelerating stochastic composition optimization. Journal of Machine Leurning Research, 18:10011110::2 2017.
[4] Zhe Zhang and Guanghui Lan. Optimal algorithms for convex nested stochastic composite optimization, 2020.
[5] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Trunsactions on Signal Processing, 69:4937-4948, 2021.
[6] Wei Jiang, Bokun Wang, Yibo Wang, Lijun Zhang, and Tianbao Yang. Optimal algorithms for stochastic multi-level compositional optimization. In International Conference Machine Learning (ICMI), volume 162, pages 10195-10216. 2022.
[7] Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. In International Conference on Machine Learning (ICMI., volume 162, pages 32922233317, 2022.
10

---

[8] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In Advances Neural Information Processing Systems (NeurIPS), pages
2021.
[9] Andrzej Ruszezynski and Alexander Shapiro. Optimization of risk measures. Mathematics of Operations Research, 31 11:433-4522 2006.
[10] Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for class of distributionally robust optimization with non-convex objectives. In Advances in Neural Information Processing Systems (NeurIPS), pages 10067-10080, 2021.
[11] Purushottam Kar, Bharath K. Sriperumbudur, Prateek Jain, and Harish Karnick. On the generalization ability of online learning algorithms for pairwise loss functions. In International Conference on Muchine Learning (ICML), volume 28, pages 441-449, 2013.
[12] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online AUC maximization. In Advances in Neural Information Processing Systems (NIPS), pages 451-459, 2016.
[13] Yunwen Lei and Yiming Ying. Stochastic proximal AUC maximization. Journal of Machine Learning Research, 22:61:1-61:4; 2021.
[14] Tianbao Yang and Yiming Ying. AUC maximization in the era of big data and AI: A survey.
ACM Computing Surveys, 15:11177:1 2023.
[15] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning (ICML), volume 70, pages 1126 1135, 2017.
[16] Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. VAFL: a method of vertical asynchronous federated learning, 2020.
[17] Christoph Dann, Gerhard Neumann, and Jan Peters. Policy evaluation with temporal differences:
A survey and comparison. Journal of Machine Learning Research, 15(1):809-888 2014.
[18) Qingsong Zhang, Bin Gu, Zhiyuan Dang, Cheng Deng, and Heng Huang. Desirable companion for vertical federated learning: New zeroth-order gradient based algorithm. In ACM Interna- tional Conference on Information and Knowledge Management (CIKM), pages 2598 2907, 2021.
[19] Ganyu Wang, Bin Gu, Qingsong Zhang, Xiang Li, Boyu Wang, and Charles X. Ling. unified solution for privacy and communication efficiency in vertical federated learning. In Advances Neural Information Processing Systems (NeurIPS), 2023.
[20] V. N. Vapnik. Statistical learning theory. Encyclopedia of the Sciences of Learning, 41(4)33185- 3185, 1998.
[21] Ming Yang, Xiyuan Wei, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic compositional gradient descent algorithms, 2023.
[22] Huizhuo Yuan, Xiangru Lian, Chris Junchi Li, Ji Liu, and Wenqing Hu. Efficient smooth non-convex stochastic compositional optimization via stochastic recursive gradient descent. In Advances Neural Information Processing Systems (NeurIPS), pages 6926-6935 2019.
[23] Adithya M. Devraj and Jianshu Chen. Stochastic variance reduced primal dual algorithms for empirical composition optimization. In Advances in Neural Information Processing Systems (NeurIPS), pages 9878-9888, 2019.
[24] Saced Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal on Optimization, 30(1):960-979, 2020.
[25] Andrzej Ruszezynski.
stochastic subgradient method for nonsmooth nonconvex multilevel composition optimization. SIAM Journal on Control and Optimization, 5933):2301-2300, 2021.
11

---

[26] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochas- tic gradient descent. International Conference on Machine Learning (ICML), volume 48, pages 1225-1234, 2016.
[27] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-522 000999526,222 2002.
[28] Arkadi Nemirovski, Anatoli B. Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4)11574-169, 2009.
[29] Léon Bottou. Large-scale machine learning with stochastic gradient descent. In International Conference on Computational Statistics (COMPSTAT), pages 177-186, 2010.
[30] Yi Zhou, Yinghin Liang, and Huishuai Zhang. Understanding generalization error of SGD in nonconvex optimization. Machine Learning, 11 111(1):3453377 2022.
[31] 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.
[32] Yunwen Lei, Mingrui Liu, and Yiming Ying. Generalization guarantee of SGD for pairwise learning. In Advances in Neural Information Processing Systems (NeurlPS), pages 21216- 21228, 2021.
[33] Yunwen Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. In Conference on Learning Theory (COLT), pages 191-227, 2023.
[34] Zhouyuan Huo, Bin Gu, Ji Liu, and Heng Huang. Accelerated method for stochastic composi- tion optimization with nonsmooth regularization. In Thirty-Second Conference on Artificial Intelligence (AAAI), pages 3287-3294, 2018.
[35] Junyu Zhang and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. Advances in Neural Information Processing Systems (NeurIPS), pages 9075-9085, 2019.
[36] Jun Chen, Hong Chen, Bin Gu, and Hao Deng. Fine-grained theoretical analysis of federated zeroth-order optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
[37] Dominic Richards and Σīaa Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. In Advances in Neural Information Processing Systems (NeurIPS), pages 8609-8621, 2021.
[38] Yunwen Lei, Rong Jin, and Yiming Ying. Stability and generalization analysis of gradient methods for shallow neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[39] John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):278--2866, 2015.
12

---

A
Notations
The main notations of this paper are summarized in Table
Table 3: Summary of main notations involved in this paper.
Notations
Descriptions
S
the training dataset defined as {=1,..., Zn, ž1, ... Zm
S
St {21,... ... 21-1; 2/,, Zi+1; ... 2n 21, .... km3
Sa.5
ŞAz {21,.., Zn1 ø1 ..., 2y-1 2/j. 2z+1: .... 2mz
the number of random unit vectors the inner model parameter and its hypothesis function space, respectively the outer model parameter
W E R
Rd
9:
the inner function and the outer loss function, respectively
Fsww)
the population risk and empirical risk based on training dataset S, respectively the optimal model based the empirical risk, w(S) arg min Fs(w) the optimal model based on the population risk, w" arg min F(w)
w())
wEW
A(5(
the given algorithm and its output model on S, respectively the total number of iterations for iterative optimization algorithms the step size at the 1-th update, / [T 1]
T
m
we
the model parameter after f-th update, E [7), WTT A(S) the parameters of Lipschitz continuity on g(w), f(v), respectively
Lig Li
a
the parameters of smoothness on g(w). f (w), respectively
V,
the parameter of bounded variance on g(w)
Mg.Mr M,
the parameters bounded functions g (v), respectively
Ez
the parameter of stability
the parameter of PL condition
[-]
[m] = [1.....n] n)
the base of the natural logarithm the Euclidean norm
||-
The pseudo code of FOO-based VFL and VFL-CZOFO is present in Algorithm
B
Lemmas
Lemma 1. Assume the function is convex and a-smooth. Then, for any w, w', we have
(Vf(w) Vf(w'), w w') 2 [Vf(w) - v((w)112
Lemma 2. Let be the base of the natural logarithm. The following inequalities hold:
(a) if m (0, 1), then Σ k-m "=< -1 m):
(b) if m then Σ k-m S log(et);
13

---

Algorithm 2 FOO-based VFL VFL-CZOFO
Require: 01. wf: initial global model and local models; fou Th: initial learning rates for all t 1, 1.... T do
for all & E [K] in parallel do Randomly select a sample it E [n]. obtain Isi, (wf²) and Ves, (wr)
Send 9z., (wf) to server
FOO-based VFL: Receive V fg (wf))
Update W[+1 We The Vgz.,
(wf)
VFL-CZOFO: Receive fg (w]
Update wi++1 = Wt mh Vgz,, (w V f(2,, (w/))
end for
Server receives Iac, (wf) from K clients
FOO-based VFL: Obtain and send (gee,, (wx)) to the k-th client
VFL-CZOFO: Compute V [92,, (w/)) and send it to the k-th client
Obtain (uz) and update ur+1 Ut 170 V (wr)
end for
Ensure: K final client models wi...,, w
(c) if > then Σ mm m=
(d) Σ
S log(t + 1), where hip 2 1.
kthu
k=1
Consider the gradient-based optimization method wr+1 w/ - vy (wwr). For two iteration sequences (We)tE(T) and [wi if the function (w:) is p-smooth, m S 1/(2p),
Lemma 3.
37
38
and the minimum eigenvalue Amni (v2 (v²f(we) 2 then
(wo w/t, V v((w)) V v((())
2n (1-12) 1):P (Vwe))) vf(w()]13 ellw> w/ VV((w. Vf(w))1²
Lemma 4. the function f is a-smooth, then, for any w, w', we have
1
f(w) - f(w') S (w w', Vf(w))) )) + Jalle w/ 11?
(6)
2
1 [V](w)]1 s ((w) inf sww') S (ww)
(7)
20
and
[VF(())]1 < Fs(w) - inf Fs(w") S Ps(w). 2a
(8)
w
Lemma 5. (39) Assume random vector X E I&d is d-dimensional uniform distribution. For any E N. there holds E
||| dd
Lemma 6. (39 Let uy Rd 21, b} be i...d. random vectors satisfying d-dimensional
uniform distribution. For every random vector E Rd independent of all and 3 E (0, the following inequality holds
d
23 +
g
E
c. uim Br
<
||
14

---

Table 4: The main differences among our main results (wx) = vo(wr) Ei= Ind (f(er+1 tu
un,1) - f(rr+1)), fe(we)) = E'= Hed (g(ws + pum,) - g(wi)) (f(1+z)), vfs(ur) =
1 Ei= Hed (f(14+1 + pwaa)) (( Ei= wid (a(w: + pmn,.) g(w)))).
1
Results
Generalization
Optimization
Thm.
Co-coercivity
Thm.
Almost co-coercivity
Thm. 4
(wxs)
Special decompositions of V
Cor. 1
fu(s))
Special decompositions of V
Cor. 2
Combination of Thm. 4 and Cor.
C Proofs for General SCO
Proof of Theorem 2
(a) SCGD: As Definition
I we define S
= fzi... Zn 21..., /.m Si.z
(z1, 21-1 2/, 24411 En 21; -.. _m3
and S
{21, Znr 2l 21-1; 2). 2,+1s ...y 3m
for any i E [m], E [m]. The two terms EA
[| WT
4.2 and EA
|T w will be
estimated as follows.
EA WT wp d==
There are two cases that need to be considered. Firstly, when A i, there
holds
8,2
Wr+1
1
TJe Ven, (w)) fzz,, (U++1) + T/6 Vg,., (w, ) fz, (u > ||²
Wt (
(f 1|² n/ Vgz,, (wr) Vaz, (u++1) Vgz,, (w) J3n
21 ( (wi wht Vga,, (w,) V fz, (2++1) Vg..,, (w + V fz, (211))
Due to two properties of the function f(g i.e., convexity and smoothness, Lemma implies that
Wy - w f Vga, (we) V s/ (ve+1) Vga,, (w) E,, (off1))
1
B W0 wh Vgzn, (wx) V [zy (9zu, (w+)) Vgzi, (w: SEz, (0z,, (wz
V (we) V (9z,, (we) - Vgzn, (w) 1.3 V VJzz Jz (9.y, (w 1.2 ))
2 0.3
where BV (V2+1) = V S2s, (9zz, (w:)) based on the update of SCGD. Then,
W/ - -w 1
1,2
2
m/a
21t;
Voz,, Vf,,, (gzy, (wi)) V Vez, ( (gzy, (uff"))
+
82
a.
W/ i
28 where the second inequality is caused by 1/2 < ot < a. Secondly, when i = i, there holds
29
That is We++
wi41
f.z
1xx w
W141 - w/+h
15

---

17 v (wi) Vfz, (u(+1) + 17s V (offi)
Wt
w
VI
W1
+ a/ V | (w)) V J3 (1++1) Vgsi, (w, V (of+t)
VA
Wr w
+ 2/ke V (w))) V (vr+1))
VA
W1 w
+ 2 ,
Combining the above two cases, can get that
Mo++ wi+1 - w2 wi
Li + i] + - 1.2 + 2g L 1/6 - 8).
-ww-
Taking expectation over de.
E2
W+++
Ei, [1 + ell + I0o wftt + 2L, 2 Ei, [i]i, = i]]
W0
2g T.S np-
VA
W1 w
n
Then, taking expectation over A and taking summation from to T to get that
2L L m
EA wr - w6
<EA
Wr-1
77
T 2L
17c
t=1
4Lg , 8
T-1
Σ
on
Abg 1 log(eT)
an
where the last inequality is from Lemma 2 (b).
2) EA
WT w
Firstly, when je # j. there holds
1.3 w
W++1
W/ w 1.
V 92.. (w;) V. (1++1) + Tee Vyn., (w) 3 1V S2,, (v ||²
Wt ?
+ T/e Vgz,, (wy) V (M++1) Vgzn (w 1 V (o2 |
21p: (wr wt Vizu, (w,) V (v++1) - Vgz,, (w) S (o441))
Due to two properties of the function fg(()), i.e., convexity and smoothness, Lemma implies that ) V fz, 1v++1) Vige. (wl V Vs, (u(f1)
Wr- w 1. Vgnn, (wx)
1
We wh Vg.., (w)) fz,, (gz., (w:)) Vgz,, (w) V fE, (oz., (w)
B
1
Vga., (wx) V f (g.., (w:)) Vgn., (w- V fe, (9x,, (w )) 2
03
where BV (1241)
V SEy (9zz, (w.)) based on the update of SCGD. Then,
wh1 W2+1
|
w++1
2
2m
(.3 [gg., (w: (ge,, (w:)) Vga., (w. (gz, (w
W/
+
g2
16

---

< W
where the second inequality is caused by 1/t S at S 22. That is [ - 5 22 m Secondly, when Je = j. there holds
28
W++1
1+1
w.y
T/e V Da., (we) V fzj, (u++1) + The Ven. (w) (w) V (w(+1)
w
+ 778
Vez (w)) V (u++1) Vgz., (w) V (ui+1)
VA
w
+ 2m.
Vga., (we) Viz, (*++1)
IA
+ 2T T.
Combining the above two cases, we can get that
W++1 w - $ 1
ut 4i + -
51+ (/10g - wp.² -w?"" + 2L Ulje = j).
Taking expectation jt,
E2
Wr+1
w/44
w!!"
Eje [ F 51l + (1|u
wpt6| ( Ej, [[,e all
2 2g I-f Th.
w
Then, taking expectation over and taking summation from t to to get that
2 Ls
EA
WT
w
<EA
WT-1
w
6.5
1/e
m
T-1
2T I.g
m
4Lg L 3
T-1
am
LggL8Blog (lg(eT)
(b) SCSC: Similar to the stability proof of SCGD except for the equation Vfs, (1441)
V fzz, (9s,, (wx)) based on the update of SCSC, we have that, for = zt
2 < 2
4L Ly log(eT)
EA
WT
w/
an
and
4L L log(eT)
EA
WT w
Proof of Theorem 3
SCGD: 1) EA
d.z Wr W7
Firstly, when i, * i, there holds
6.2 T/e Vgz., (we) VS2, (V++1) + m/ Viz,, (1/:21
Wi+1 w++1
Wy wi
17

---

Wt uz." 1/ + 1/6 Vga., (wt) V/ 53, (vt+1) - Vga,, (m) Ri V 13, (0
|
2nd ( (rr wh? Vgz., (w)) Vzz, (2e+1) Vgz,, (w) fa, ( (o)=1)
Without the convexity of the function fz)))). Lemma can not hold. An almost co-coercivity of gradient operator (Lemma 3 is introduced to build the relationship between the inner product
term
We wi
Vg.., (w,) V fe, (v++1) Vin,, (wf fa,, (D/41) and the two squared terms
With Assumption 3 the terms (g(w;) and V 1 are both differentiable. Thus, V[((+ is also differentiable. which means that it is continuous on its domain, As we all know, a continuous function has primitive functions. Then, it is reasonable to assume that there exists a primitive function f(ws) at least whose derivative function V f((r) = (g(w))Vf((++)) For example, 3 (v(+1) is one of the primitive functions f(w,). Then
w/ w. V (w,) V (+++1) Vga., ( Vf,, (1 f.a
2
W/-1 #
|wee w -1] v/2
24 (wx) Viz, (w/tt)/
2n1 ( we wh V fe,, (wx) V foa, Ri (w)²))
(9)
Taking derivative of V S2a,, 13, (wx) over wt. we get that
V2 V2fe, E. (wi) V&ge., (we) Vzz, (Uo+1) + VVs.,, (w:) V2fz, (1241)
Vo ( (we).
Thus,
v2 V' (wm) S aggs + 3L
Let agg then s, singular value of 2 #i. .i. (we), can know that Amin (v2 1,, (we) 2 V22 fe, 13, (we) 2
5,, (wi) is p-smooth. Since V2 (wx) equals to the largest
-p. According to Lemma we can get that
Wt W/ V Fag (we) V Vrn 2n (w)+t)
221/ (1
P7te | (wx) Ving 2, (w: 1|2 - p W: w VizNi,, (w.) VS (uf
2
-21 (1 PT){
| (w.) Vizu in (u ( 1|?
W++1 wii |??
2
Now, plugging the above inequality back into Equation yields
6.2 | W1+1 - wz+1
W/ w. 2
+ (T? 4n72 (1
PT)
))
V 24 53, (w) ( Vu,,,, (wt
wc+1 w
2
Wh wi 1.2 2
+ 2pm,
|we++1
w
1,z
2
where the second inequality is due to mi
1
<
3.
The above inequality implies
2pt
2p
W - 5 VI
wi+t
w/
w 8.=
2pm
Secondly, when it = i, there holds
W141 - wf+f
18

---

ti v (w)) Vfs, (ut+1) + 17s V (offi)
Wi
w
VI
W1
+ t/ | (wm) V S3 (u++1) Vgsi, (w, V (oi
Wi w
+ 2/te V (w:)) Vzzz (vt+1))
VA
Wy w
+ 2 ,
Combining the above two cases, we can get that
[+++1 1 w
w2 wi? 1.2
The i] + (1|0 wf + 21g + I.971) Tle = =).
VT- 2pm
Taking expectation over iz.
Ex
1.2 W[+1
W1+1
Ei, [T. # i]] + (11x - + 2. T.(11)
Wi
W/
Ei, [ī = i]]
2pr 1
1
2L gg n
w
VI 2pm
n
Then, taking expectation over A and taking summation from / = to 7 - to get that
1
2 Ls
E,
WT
EA
WT
w
+
1/.
2pT
n
T-1
2 1)c
2pne
11
1
Li 1
pn
1
Lg 1
pr t
T
T.gT.s 1
exp
1'
pn
Lig Tog
Σ
exp
pr
Lg LgL log(eT)
(10)
pm
where the fourth inequality is from ex 2 1 +
2) E,
WT w
Firstly, when je * j. there holds
Wx+1 1
w
The Vynn (w)) V.z, (11+1) + m/ V9s., (w) |4 S3, (1441) ||
W/ wtt 1.
Wt wxt
j.2
+ Th
Viz,, (wy) V (V++1) - Vyzi, (m) 1. 12,, (1f+1) 2
2m (
w. 1e,, (w)) V fz, (1(+1) - V (w 1.3 V fz, (o(+1)
We assume that there exists a primitive function ((wx) at least whose derivative function f.(w)) Vg(wx)VV(VE++) Then
W141 w++1
19

---

|ws wp/ia + t Visa, Ri. (we) V/ (s,, (wg 1|
2111 (m) w²* Vfzu, 53, (wi) V 8 (w):")
(11)
Taking derivative of Vf R3, (w²) over wt, we get that
V 12 (14) V2 (w)) V (v++1) + VVz., V2 V2 (vL+1)VVle (we).
Thus,
v2 Sen (w01) S aggs + BL
Let P aglss + a then S2n,2, (we) is p-smooth. And we know that
Amin
(22 2 - /2 s Ss (174) 2 -p. According Lemma we can get that [er - wffi -uf,, V. (w)) - V Van,2, (w)-3)
2217 (1 (1-Ph) / (w)) Vfzi, s. (uzf ||e p w w Vi (wi) + Visn (ufit)
-21 (1 ( V (w:) Vfzu Ene (w./ ||?
W whit
Now, plugging the above inequality back into Equation
yields
wff11 ||
W
x W/ w/ j.2
+ +(12
4n (1
PT] ) 2
Vaa (w)) (w /| 2pm |wu+1 - w(+1
2
W/ wft"
+
2pm
W+++1
1.2
where the second inequality is due to 17t S
1
S
3
The above inequality implies
2p1
2p"
W with - 5
Wt w
VI
2pm
Secondly, when ji j. there holds
W/ w
j.z [++1
ne V gz., (w)) V fa, (u(+1) 17s Vge,, (w V (uff11)
W/
w
V Vgz, (w)) VJ,, (U2+1) Vgsi, (WF V fay, (of
W/
17
Wt f
2m
Vgz,, (.: (v++1))
VA
We + 2LgL,
Combining the above two cases, we can get that
01+1 w
1
wi w [[i
# 5) (1wv wf:3| + 2T I. Tīj j).
VI
2pm
Taking expectation over jr.
Er
1.8 We+1
w
We w
j.2
E2 [T * 5]] + [[w> -w + T. R2 Mije = إl
2pm
+ 2T T.s mc-
1i w
VI
2pm
m
20

---

Then, taking expectation over A and taking summation from t = 1 to T 1 to get that
1
2 L
EA
WT
EA
WT
wT--1
V1
2pT
T-1
1
2L Iug
1/t
201
m
1
Lghss
t' 1'
pm t
1 1- 1
L 1 pm t
T-1
T
L.g L 1 pm t
II 2
exp
t'
15
T-11
1
Tight
t' -1
pm
Lg y (cT) log(eT)
(12)
pm
where the fourth inequality is from e* 2 +
SCSC: Similar to the stability proof of SCGD except for V Sa (wx) = yeg (wx) V Szy (ve+1) +
Vgz., (w,) V² fe, (1++1)Vgle (we) based on the update of SCSC, we have that, for The S 2pt S
2p p = agL, + Ljay.
3.
T. [Tgl log(eT)
EA || ur m/ |] S
(13)
pn
and
|| WT -
[] <
Lg L y (cT) log(eT)
EA
(14)
pm
D Proofs for Black-box SCO
Proof of Theorem
SCGD: 1) EA
8. u7
Firstly, when it A i, there holds
2
6.2 Wr+1 Wx+1
17c V (wr) V fz,, (v++1) + 17t go., (w) ( V (ofti)]i ||
Wr - w
Wr w6 |
+ v/2 V (w.)v/) (Ve+1) Viz, (w, 2 V2 (o2f1))) ||
277. w3
w. Vgz.. (wi) f. (er+1) - V (w V (o1+1)
10 - wu?:21 11 + 7/ Egz,, (wx) Σ
Ued (fzz, (ve+1 + pmne)) fz, (v141)) Voz,, (wi
1=1 a
1 Uzd ( (f,, (otii + pmve)) fa, (vftz)
21

---

b 1 2nt wt w Vgaae (wre)
Σ 1=1
Wed
(fzz, (Vr+1 + +uu,,)) faze (vc+1))
VVz,, (wft
(Jez (vif2 + pmu,)) Sāz (v
1=1
With Assumption the terms Vg((e)) and f(1+11) are both differentiable. Thus, ff Meil (f(r++1 + pmm,)) - f(++11) is also differentiable. It is reasonable to as- sume that there exists primitive function f(wr) at least whose derivative function vf(we) = [g(we) Ei= P
Mad (f(v++1 pm),)) - ((141)). Then
W 1 - u1t1
We w 11= 1|22
+ n Vi (wr) V. (wp+) 1|²
2770 we w/ Vfnn (wi) - Fan (w(²))
(15)
Taking derivative of ff Ry (we) over wi, we get that
2 fa .3 (we)
22 gen. (we)
Uel
(fe, (Ut+1 + prw)e))) - Se, (v241))
b
Wr.1 (VJs, (Ve-1 + (uue,)) - VSz,, (1++1)) Vgl, (w²)-
+
VVz.. (we))
b
1=1
Thus,
12n, (wx)
f f
1 22 92:, (we)
Σ
2es
(Jzy, (Ve+1 + praee) Szy, (u++1))
b
+ BV gane gan
(wr)
(V (U++1 + pmle)) - Vfe, (U++1)) VoLr (we)
2 Uzi
(wx)
W4ll
(Jzz (1e41 + pmle,) - Szy, (v=+1))
1=1
+ VV (w))
Σ
ue.
(V.f,, (1 + pur,)) Vfs, (U142)) Vgl, (wz)
4
(a + 31,M,
Let 1 (agMi + 333,,)). then fennen (wr) p-smooth. And we can know that
Amin (V2 (V2 (we) 2 - 1| fen, (wr)) -p. According to Lemma 3 we can get that
we - w/ V. 2zn (w)) V 23, (wfit))
221// (1 pT)
V (wa) Vie,e, (u 1,2 1|2
whe VJ (wx) Vie, 25, (wf
2
-2m
(1 - (T){
) Vi (w:) Vf 3y (w 1, ||?
W1+1
2, w
!?2
2
22

---

Now, plugging the above inequality back into Equation 15 yields
4.2 |
Wt+1-
wi+1
<
W/ w/ 2.2
+ (1ē
41/2 (1- pil
)
V Sen (wx) (w:)V 82 (ut²)
/|
2
2pmp
|w++1
wi+1
2.2
2
<
W
wi x
+
2pm
|oeet1
f.2 w
where the second inequality is due to 11e S
1
S
3
The above inequality implies
2pt
2p"
h2 w/41
5
w.
6.2
vI 2pm
Secondly, when i, there holds
f.2 W(+1
w
w/
mie V I2., (we) fa (0(+1) 17s V (w,-))/ (o/t2
10
w #
Voz. (wr) V S2,, (u2+1) Vist (w. (. V (3tt
10
+ 1/2
Wt
w -
+ 2nc
Vg (w)) || (,,,111))
00 w
1
2I Ms np-
r
Combining the above two cases, we can get that
|We41 wHil| VI 2pm2
We w
liee # o) + (1us wp
2Ig M, m7 4
lile 1).
Taking expectation over it.
R,
W1+1
W
1
EF, (T # i]] + (I (1100- 2/
2L Ms me Ri, [T[.. = s]
W/ wi²"
V1
2prp
1
d.2 w/
2g M m
2pm
pm
Then, taking expectation over A and taking summation from t to to get that
EA
WT w/
EA
WT
1.z wT
||
Mg m
1p2pph
2pTh
pn
MLy T
V1
2pme
jmm
WEt+1
Lg pUm t
8'
M Pun
t' 11
1'22
M 1
exp
ppm
P=2
L. My
Σ
7
exp
pnm
1=2
t=1
23

---

Mg log(eT)
(16)
where the fourth inequality is from e" 2 1 x.
2) EA
WT
=/e Firstly, when je # j. there holds
Wh+11 wx+1
T/. Vg, (we) V Sz (v++1) + T/e Vgla, (w ( Sz,, (v/ti)] ||
W/ wi
w
1
Vig.. (w,) V.,) (u++1) Vgu.. (w/² S.. (ubtt)| ||
W:
207e
w
w
gzn. (we)) f. (e(+1) - Vizua (w,² *5 V (cff1)
We
+ v/
Vgz., (wrt) Σ 1=1
Und
(Jzz, (1e+1 + pmme)) Sz (1++1)) Vgzu, (wt(²)
p
1 Wt.1
(JEr (uff2 + prae,))
Szn (m(f1))
5
1=1
b
1 wht Veen (we))
Σ 1=1
Hil (Jzz, (1o+1 + pun,) fzz, (v(+1))
2n
b
Vgz (wzt))
1
Hell (Se (vits + pmue)) Szy (wbtt))
With Assumption 3 the terms Vg(ws) and (((41) are both differentiable. Thus, Mad (f(141 pmm,)) - (((+22) is also differentiable. It is reasonable to as- P
Vg(wi) E sume that there exists primitive function f(wz) at least whose derivative function vf(w)) (g((e)) [ 2ad (f(1441 + pm),1) - f(14+1)). Then
P
Wx+1 w 1
W/ u =|=
+ nhe VI 5 (we) V Van, (wx+:) !|?
21/r (wi w/t V V (wr) V Sea, 2n (w)(²))
(17)
Taking derivative of Vfz,,18 (wi) over wi, we get that
V S (w²)
= -V (1))
Σ 1m
Ued (fz, (ve41 + pmee,) - fzy, (1141))
b
1
Vell (V (wo- pue.)) - VSay (Ve+1)) Vgz, (wx).
VVga, (w²)
Thus,
2 3/ 13
(wre)
2330
2 V2gee yois (we)
1
Σ
Wed
(Jz, (Ve+1 + wale)) Szy, (u(+1))
b
1=1
b
+ VVg. (we)
1
Ur
(Vis, (Vet) + pma.)) (v642)) Vo (wx)
1=1
24

---

b
2 g
(we)
Σ
Wel
(fe,
(v1+1 + pmm,,)) - fæg (1++1))
1=1
+
VV VV Izz, (wrz
Σ
We
(Viz,, (11-1 + pml Vsz,, (12+1) Vosr (wx)
1=1
1 (n M + 31g
Let
(g + ,1I then Say,2,, (wx) is p-smooth. And we can know that (2 (2 (wz) - V2
-1| fen, Ris (us) 2 -p. According Lemma 3 can get that
Amin
Wt - -wfi V.en (w)) V Vfan 8, (w)(i)
2,17/ (1 11P
P ) / (w)) Vizu Sn (uzf 1| p wt w
Vieni (wi) + Vien (ufit) 1
=21p (1 PT)
2 )
[iar, (w.) Vfzu, E/e (w ||?
p W w
Now, plugging the above inequality back into Equation 17
yields
3.8 2 W/+1
w[+1
+ +(1
4n² (1
PT) )
V R2 V 8,
(wp.t)
2pm | - w ||
Wn
W1:
2
2 +
|
Wi ws
20m
u1t+1
wi+1
where the second inequality is due to 1) S
1
3
The above inequality implies
2pt
2p"
Wi+1 -
w(+1| 5
J.2
VI
1pm2pm
Secondly, when ji = j. there holds
w w
F/e V Iz., (we) 4 V/z,, (u++1) + 7/s Vzzz 1V55) (vitit)
W/
w.
W/ w =
V go., (we) V fe,, (ue+1) - Vgnn (wt f. (ot+i)
+ 1/
W/
m
+ 2T
Vgz,, (w:e) [5
VA
We
w
2L,Mr 4
Combining the above two cases, can get that
W141 w
We w Ilea #1] + (Iu: ([u=-1 +
mp
M
2I. M₁ m1
Ilse 5).
V1-2pm
1
Taking expectation over d2.
1.5 uz+1
w
1
Ei, [Lee # jll + (Iwi- wp + 2L M, m) E., [4 = j]l
V1
2pm):
1
2L M, nt.
j.z
W/ w
+
V1
2p1
pm
25

---

Then, taking expectation over A and taking summation from t = 1 to T - 1 to get that
2I Ms pum
EA
WT
wT
5.8
EA
Wr-1
WT
1.8
+
n
1
2pm
T-1
2Lg 1/t pum
2pme
Wel+1
M ppm t
1+ t' --1
Lg
mpm
T-1
L 1
exp
pum t
P=2
T-1 Σ
M
T
exp
puu
Lg M (eT) log(eT))
(18)
pum
where the fourth inequality is from e" 2 11+1. Z.
Next, will study the optimization bound. According Equation 6 in Lemma f(,)
VV((u) (w)) (VL+1), second-order Taylor expansion, Lemmas and 6 we provide that, for any
p 2 V2,
E
(w) - Fwr)
1 (wi+1 Wi, (Fs(w))) + z 110c11 - mill3
<
7/ Vg.., (w)) (w)) fz, (1) VFF((u))) 1 + n Viz,, (wx) V (Bs+2) 1"]
=E
(FiE, (1e+1) - (p+) 1) 1) /V sV (1(+2) + (pt 2 2) BV fz, (we41))
E
Vo (1m)
x ny VeVez, (wx) (Vizz, (1++1) - BV (v++1) + VV fz, (eet 11
1
FF((W))
+
V9zz, (wx) (T)Es( (w++1) - (p+ 2) SV (1t+1)) VFs(ws))
<E
1/
2)
1
ne n.llFF(( + ami Voc., (wi) (Viz,, - BV BV ( (o,,),( (1
pp + 2
+ on/
|| V (w:))l
1 2 BV (UL+1) )1( + n [Vss()))
<E
2 Tt
1
Vgz,, (mm)
(Vis, (1041) - p+
1
n: [[)((( + an? |oz. (wi) (Tiz (v++1) - fV, (ot+a)) |
(
+
an? (w))
1
|o=., (w:)
(FiE)) (12+1) - (pt 1 2)
17 /V fz, (0(+1)
2
26

---

(Ttz, (0142)= - f3 (0(42) )19 + (aan - pmm) E Fl
+ am E
gzn, (wre)
1
Vgsie (wi)
Σ
Wed (1c41 + pme,)) - Szx (vc+1)) - (pt 1 se (ue+1)
2
1=1
+ an
Vgaue (we))
Σ
Wr
(fzz (1e41 + pmlee)) - fay, - - (vet1)
b
#
1=1
+ (am?
pmrt) E [1] V Fss()))) 11
1
Vglce (wz)
: Σ
(Viay, (oc+1), uns) we, +
H (H(N))) (V" (v)lo=ui wes usss)
2
pp 2+22) 1 /V fe (ve+1) |1
+ an B
Van (we)
(V.fss (vc+1), ued) vell
1=1
+
L (wei) T 22
szy, V25zz,
(u)lu=u?11..11 wel
f2z, (tt+1)
+ (am? pme) E [IV
2
< (2am² + +1²) 1
1
Σ
h
1
(ue,))
V2 Szj, (v)) (w)l we,1 we.1
27
b
2
1=1
+ n/EE
V9zne (wr)
1/10
Σ
b
v fa, (u++1), wes (p pp+
1/2) 1
@V fs, (et+1)
b
1=1
27
+ 2011 E
Vigzin (wz)
V (w++1), u.s) u4.1 BV S2 (1z+1)
b
+ (ank -prc) E []] /
1/t Σ
b
27
< (20mh + ni) B
ト (ue.) T V2 Sz,, (v) (w)l==r(, mes) well
||:
b
+ E
Σ
v Sz, (0++1), un.1 uns - (p+
2 2) /V SV (1++1)
6
1=1
[[(
1
b
+ 22L3n²
Σ
V (v1+1), un
una - BV (1e+1)
+ (am/ pmr) E || (wx)))))1
b
27
< (2am? + no) L
Σ
(ue,)) T 22 fzz, (v)l He. 24.1
2
+ ( 23 + 82
+ d- (2p 1)3 (p 11)²² 32
20
E
V Sz, (1++
b
b
+ +anp -pn) E [I [|]
L3
< (anj pmt) [IV )|
+ 4
(2an/ + 17, [1/ [1
d d- 32
d 12p + 1)B3 + (p + 1)²² A²
+
20
1. / 2
+
I. T. n
b
b
27

---

+ d
< <(an)
E (1)
(2am) + 17:)
4(d + 6)
d d 23 + 82
d (2p + 1) + (p + 2)² 3² 1. 12
+
2a 20 1 2
b
Let d1 - =d d- 23 + 3² and d2 = d - (2p + 1) 8 + (p + 1)²² 3a to get that
E (FF(()(+1) Fs(w)))
S(ant mi) E ( + dLzu²ay (2amk + m1) +
13L2
(2ad1n² + dzm))
4(d 6)
b
dL3 a
(207) 2 + ni) + 1
S 2 pnd [I [VF +
(2adi + d2n))
4(d + 6)
b
dL g 1 2
12 (2ad1 + d2n1),
pym (Fs(w] (w())
(2am ++))
4(d + 6)
b
where the second inequality is due 7 is from Equation in Lemma Then,
when p v
20 and the last inequality 7
p7
2ad
Za
E Fs(w)+)) Fs(w(S))
S (1 pmm) E [F((w))) Fs(w(S))) + dlzuza3
13
(2am) + mc) +
(2ad1 nh + d21))
4(d + 6)
b
= (1 - :) E Fs((i) Fs(w(S)))
dL3x²a² a
2
1 ) + 13L13 2d
1
+ d2 pat
+
4(d + 6)
ppatt
pat)
p2ott
We multiply both sides of the above inequality by t to get that
tE [Fs(we+1) - Fs(w(S))]
dlzuzaz 2
1)
13
2dh
d2
<(t - 1)B [Fs(wr) Fs(w(S))] +
+
+
9
+
4(d+6) ppa
pox
b
p-at
poc
Then
(T 1)E Fss (wT) - (s(w))))]
di2
1
13,12
2dh
d2
S(T 2) [Fs (wr-1) Fs(w(S))]
+
+
4(d 66)
p²a((T - 1) pa
ppa
pa
T
T-1
1
2
2d + d2(T-11)
+
4(d+6)
p'at
pa
b
p-at
pa
[=1
dlz12az
2 2og((ET)
T T 1
13
2dd
log(eT)
+ d2(T 11)
4(d+6)
p²a
pc
p²a
po
That is
E [[Fs(wr) Fs(W(S))]
dLzg2ar
2 log (eT)
13123
2d, log(eT)
+ d2
(19)
4(d + 6)
Paa(T 1) pa
paa(T - 1)
pa
Combining Theorem I Equations (6). (8 and 19)
get that
[[F(wT) F(w") )] < O
( (nn + m 1) T log T + n -
+ 1² + b-1d2)
SCSC: Similar to the stability proof of SCGD except for
22 23, (we)
28

---

b
gen, gos. (we)
Σ
Well
(fe,
(v++1 + pwe,)) - fæg (vr+1))
6
P
1=1
+ b
Jzz (we)
1
Ued
(VSzz, (1e41 + mmn)) - Vfzz, (e(+1)) Vizi, (wz)-
μ
1=1
based on the update of SCSC, we have that, for me S 2pt 20:
1
S 3
1/ is (agMs + L2M,).
EA
|UT
|]
Mg log(eT)
(20)
ppm
and
Lg (eT) log(eT))
EA WT w/
(21)
pjm
Similar to the optimization proof of SCGD, we also have that
B [[ - Fs(w( (w)))
d 2
2 2log(eT)
1
( 2d, log(eT)
d2 pa
$ 4(d 66
+
(22)
p2a(TT -1)
pa
pPa
1)
where dj = d - 1, d2 = d - (2p + 1) + (p + 2)²²
Combining Theorem
Equations
20
21 and
we can get that
E [F((wT) - F(mr))))ww)))) s 50 (mn + m 1 Th log T + nn + 2² + b='d2) d2))
Proof of Corollary
SCGD: EA
WT u7 d.2
Firstly, when it A i, there holds
1
W+++1 w/+11
1) V gz., (w:) V2z,, (De+1) + m/. Vgz, (w) V f2, (1f11) |
W4 w
2
W4 wft
+ ni Agz, V (v++2) Agz,, (w : V (oif
2mp
We
wi A (w:) V S2, (1141) V.z., (w) # v fz, (vitz)
2 2
1. Σ Uel 9zn, (we + () 9z.. (wx) V Teg (U++1)
We
w/
+ np
U1.1
I2., (ut + pruee) - go., (w):*) Vfs, (oft1)
b Wel (gz,, (wr + pmm))) I2c, (we)) V VSz, (12+1)
211r
We
wi
b 1=1
V4.1
92n, (wtt* + pue.)) - 9zn, (wf+t) V fa,, (offi)
With Assumption 3 the terms f((++) and g(w)) are both differentiable. Thus, ded
Σh Li=1 #
(g(wr + (1), g(we)) (1(+1) is also differentiable. It is reasonable to assume
29

---

that there exists primitive function f(wr)) at least whose derivative function vf(w:) Ei He.l (g(wr + pua.) g(wx)) f((++))). Then
W - w We: w =12 + n Vi R2 (w)) (oneVinn
Ro (w/+) ||² 27t we - w/ Vien, 5, (wi) - Vaz, 2n (w) (w(²))
(23)
Taking derivative of V S,,,,,,, (we) over we, we get that
F2 F3. (wx)
Ur.
(V (we + pul,)) - Vgge,, (wi)) Vfzz, (v(+1)
B Σ
Ut.l
(9z,, (we pole.)) Iz., (we)) V2 ((e+1)VVg) (we).
1=1
Thus,
s4, V
Ris (we)
Ued
(Vga., (we + pule)) Vga., (wz) Vfs, (12+1)
8
Well
(gzz, (we + pma).)) - I2., (w+)) V2 52 (v++1) Viln (we))
Ve.1
(Vg.,,
(wo pmm.)) - Vgzi,, (wx)) Vis, (0L+2)
B
Ued
(gzz, (we + pmas,) - 9o., (wi)) V2 fz,, (1++1) Vgle (wr)
1 g + Myp
Let = 1. 0 Mg + MgL,)). then len, (w)) is p-smooth. And we can know that
Amin (22 f2,, (wx) 2 - V2 (wx) 2 -p. According Lemma we can get that
W - - Vl F3 (w)) - v Vsz (u)+t)
2211 (1
PT]
V (aaii Rn (w,) Vfe, En (w (uf 1| - P
Wi w Vfan R, (wx) + VS En (ufi2)]
2
=21/ (1-
pT)
Vf
(w.) Vf (w x
W1+1 w w |
2
Now, plugging the above inequality back into Equation 23
yields
1.z ||² wi+1
W++1-
<
W/ w
1
2 + ?n 4n (1- - 2
pmk)
)
V Vs (wx (w:) (wt
||
/||====- 2pm
|wet1 w
wi w.
+
2pm
|
we+1
2
where the second inequality is due to 1/t
5
3
The above inequality implies
2p0
2p.
We w 6.8
W++1
wi+1
5
VI - 2pm
30

---

Secondly, when in = i, there holds
W++1 - wi+1
1/e V I2., (w)) V fz, (e(+1) + 1/s V (w)' fe, (eft1)
Wy
W
VA
W1 wi"
+ m/2
Vgzu, (w,) V VES, (U++1) Vg.i, (w) (wo V (o
IA
W1 w
+ 2T.
Vgz., (wez) [[ (1++1)
21, Ma 7)-
VA
10 w
Combining the above two cases, get that
| 4.2
s VI- 2pm
We w
lhe + + (11= w
2T Mg n1 Pr
llee = 8).
Taking expectation over iz.
E
W1+1
wi+1
1
E,, d + él] + (11001 uz
2L 2 n1 Er, [I] = i]]
w."" W/
2prz
1
4.= 2L M
w
np-
2pm
pm
Then, taking expectation over A and taking summation from / = 1 to T - to get that
EA
WT
wy
8.=
2pT EA
w/-1 1.2
||
2L Mg
T-1
2L Mg 1Jc
VI
2pme
pm
M
aum
MEt+1
L
8 1-1
pun
T-1
1
M.y
exp
pnm
2=
T-1 Σ 1=
M
Σ
g
exp
7
Ly (eT)) log(eT)
(24)
Mun
where the fourth inequality is from ex 2 1 + x. 2) EA
wr w
Firstly, when je # j. there holds
d. V Iz., (w)) V fs, (v++1) + Ths V (w( ) V. (2//1)) | ||²
We+1 1
w
w 1
We
We
w!
n Viz, J (v441) &gz, VV (0f:3))
31

---

(wi w.. Vgz.. (w, fe,, (0t+1) - Vge., V (0/=1)
277
were
w
+ n
Wed (gzu, (wi, + poae.)) gzs, (wi)) Vāzz (21+1)
1
Urll
(zc, (wp + puae,)) g (ux+:)) Vf2g. (15+1)
5
1=1
Wel (gey, (we + prae.)) - g2c, (we)) V Vfs,, (12+1)
277
Wp
we
M
1=1
Ued 1
Izi, (w?² + (ulee)) 92z, (wff+) Viz (v
b 1
With Assumption the terms f((++t) and g are both differentiable. Thus, Ei=1 P (g(wr + pmu,)) - g(we)) f((+42) also differentiable. reasonable to assume that there exists a primitive function f(wr) at least whose derivative function vf(w:) = Ei=1 aid (g(ws + pma.)) - g(w))) V (1++1) Then
Wh+1 w/11
[10 wpii 1|
+ The Vf (wr) ff fan (uf !|?
2nt (wr: - w Vizu (we) - V Vennz (w((²))
(25)
Taking derivative of Vf,, &, (wx) over we, we get that 4 F2 F, (wx)
Ut.1 r
(Vgzi, (wa pmee,) Vgai, (w.)) Vfz, (D4+1)
b
Ut (g2:, (we + pmle)) I2., (wi) V2 (0++1) Vol, (w²).
Thus,
2 i 2os Rzs (wei)
Uhd (Vgzn, (we + pme,)) - Vgz,, (we)) V fzz, (1141)
Mell (gzz, (we + pua..) 92., (w:)) 4 Szz, (Ve+1 Vol (wr)
f
6
Wt.1
(Vgz,, (w; + -uee.) V (wa)) Viz,, (cttta)
8
Upd
(ges, (we + pmle)) - Ion, (wi)) V2 (Ve+))V Voe, (wr)
b
P
1=1
< (BL.ge My + TT)
Let = 1/2 (3Lga, + M,TT),, then Pzy,Ez (we) is p-smooth. And we can know that
Amin (v2Sen),,( (wx) 2 - V (wx) 2 -p. According to Lemma 3 we can get that ww - wf.² v Vien,e,,
25, (w.) - Vi2, 3, (uf:²)
32

---

221/: (1
Vinne (wx) Vie Es (uz²²) 1| p
w w f. V 3s (wx) + V 2i (w?
2
-2m (1- - PT]
/ (wx) Vfz,, E. (uz+)) ||? We+1 ux+1 1
2
Now, plugging the above inequality back into Equation
yields
3.2 [+1
Wc+1 w
up
(nē²
4n/ (1
PTn
)
V 2i,,,, 8y (wr (wr (w/=
2pmr
|wutt w |2
W/
2
1. 2pm
11++1 wi+ |
Wy w
where the second inequality is due to 1/1
S
1
S
3
The above inequality implies
2pt
2p"
Wi+1
w1+1
J.
5
We
w
3.5
vI 2pm
Secondly, when je j. there holds
W++ w++1
T/e V g2., (we) V fa, (u(+1) + 17s 9ez, ( V (wZtit
W/
W/
w
+ T/
V g (1e) V SE, (u++1) Vg., (w) (ot
V ( (c++i)
W/
w
+ 2m
|gz., (wre)
2L Mg 1)-
IA
Combining the above two cases, we can get that
|| Tii # 51 (Iu= - -wtit +1|
2L M m1 1 j].
Wh+1 w
2pm wi wt
Taking expectation over is.
E,
w++1
1
E, [ * jll + (110:- - wp
+ 2L,M,
wi
E;, [1]i = 5]l
1
2pm
1
2L Mg m
W/
+
VI
2pm
pm
Then, taking expectation over A and taking summation from f = 1 to T
to get that
EA
WT
<
1
EA
WT-1
1.2 w/-1
||]
2L Mg m
VI
-2pm
pm
T-1
2L me
V1
2pmr
pm
WEt++
T-1
M
t'
w-11
ppm
e=++1
My mumm
1'
1
V=2
T-1
My 1
II
exp
pum
P=2
33

---

T Mg
exp
t
pjam
(eTT) log(eT)
(26)
pum
where the fourth inequality is from ex 2 1+ I.
Next, will study the optimization bound. According Equation 6 in Lemma f((,)) =
we provide that, for any 3 Fig(wy wp) Vf second-order Taylor expansion. Lemmas and 6
P 2 V2.
E (1(()))) - [s(w))]
(Wi+1 we, ((se))))) + 20 |102+11 -wall²
<
=B
1/c V Vana (we) V fzy, (ut-1), Vl's(ur)))
+ マ
1
n/ V (we)
(WW))//. VSzaa (0e+1) /
E
1)
(8ozeg (wxe) - p (レ- \
1
BVg.n (wez) + ( こ/ 1
BV VV (wx)) Veee (vet1);
+ 2 nh (Feen, (we) - -V (wr) + 3V 92.. (wi)) V Vieg (16+1) 1"]
V (uz(w))
<B
- 1/(
((50r) (wx) (wx))
(p-2)
VV (wx)) Vi2,, (v++1), VFs(ur))
p +
1)
[+F((w)))) + an?
annil((5g))) [ (ws) - Be (wi) V fis, (0c+1))
2
+ am!' || V [
<R 2 ( (ooz, (wx) (p+ 2)) (V (wi)) VJz,, (Wet1) /|
1 + 2220 | [|VFs())))
1
(p+ + 2 ne n [VF((w)))] + ani [| (we) - BV ge (wee) Vle,, (v++1) ||
+ an || [V=)(
1
||( ( (wr)) - 0 (2+2
1 2 BV
VVg.,, gz., (wre) Viz,, (ve+1)) |7]
- IF
+ am? F
[|( (wxz - BV (wx)) Viz,, (12+11)1
+ (ank - -mm) E [[[V [1(
||
27
1
We.! (gzu, (we + puee)) Io., (we)) p 2) DV (ure) VSzg, (1e+2)
2 TE
Σ
||(( 1
Σ Wesi (gen, (we + pure)) gon, (wi) - Sg (wz) Vian (ccae)))
+ an
+ (an
- -pm)) E [|| (Fs(w:)11
b
1
b Σ ( (Vgz., (wi),, ue.1) uhs + (ne (wu.)) T V22 Vzg..., (w) (w)lw=u u.l))
-2 E
1=1
(pt)) 2 VV (we) ) VSE, (1642)
+ an
1 6
Σ
(Vgz., (we), ve.) und
34

---

+ ((ur))) T V2 gau, (w))l-w;; wrs) u4.1
BV yeu, (Vr=1) V VSese (12+1)
+ (anî- -pnt) E8 [1 /Fs(()))11
ト 1p( (w,e)) T Voyzo yo., (w)l me.)) me,
< (2am) + ne) 133
+ m
Vg Vg2., (we), ve.1) ued
p (p=}) 1
geie 2/2 8 gese (we))
b
+ 22T33nfT
VVz., (wre), u4,1) we,1 - 9V (132)
+ (an) - pm))) E V (w:))1
02 (20r) + 1/: n1))E [llue,1 119]
S <(am? mi)) E || (w))))
4
-4-20 dd + 3
d d (2p + 3)3++ + (p + 2)²² 32 Linn
[1| VIV (w=)
+
dT3, 20 9 (2am) + 71))
$ (an? pi) E
+
4(d + 6)
23 + 82
2a 27 + d- (2p + 1) B + (p + 1²2²²² 3² 1.
+
b
b
Let d1 = d 2/3 + 3² and d2 = d - (2p + 1) 8 + (p + 2)² 3² to get that
E (FFs( (w((w))
d
1213
$ (ank - mm) E
+ 4(d 6)
(20r) 2 + m²) +
(20d11² + d2m))
b
1 S pm [V+s
dL33u²a3
+ nT) + L3113
(201l
(2ad1 + d2w))
4(d + 6)
b
dL 41 a
L2L2
PYME (Fs(w,) Fs(
(2am) 2 + +1)) +
(2ad z + d2m)),
4(d + 6)
b
where the second inequality is due to n from Equation Lemma 4 Then,
Fy 2at
1 S
p
S 2a
when 2
/2x V
3.
and the last inequality
E (s( Fs(w(S))
dL3ipa0g ag (2an) + ne) + (2adi + d2n))
12L3
< (1 pm)) E [Fs(ur)) Fs((w(S))
4(d
(1 1 t
aL gg
2
1 1)
D3
2dh
+ d2 pat
E Fs(w:) Fs(m 4(d + 6)
+
+
Pat2
pat)
b
p2atz
We multiply both sides of the above inequality by t to get that
IE [Fs(we+1) - Fs(w(S))
<(t - 1)E - Fs(w(S))] - dl37p202
2
1
I.2..3
2dh
d2
+
+
+
4(d + 6)
(a
pex
b
p2al
pex
Then
(T 1))E (WT) (S(w
35

---

dL d
1
Lig7
2d
d2
<(T 2) [F((W-1)) - Fs(w(S)))
+
+
+
4(d + 6)
p2(TT
1)
pa
p2a
1)
pa
T-1
2d1
d2(T-1)
Σ p-at
+
6)
pa
p
pa
1=1
d
(log(eT)) p²a
T T-1
221 log(eT))
+ d2(TT - 1)
4(d+
pa
pºa
pa
That is
B [[Fs(wr)) Fs(((()))
d 4(d +
2 2log(eT)
12
2di log(eT)
d2
+
(27)
pT - pa
pTa(T - 1)
pa
Combining Theorem
1
Equations (24). (26) and (27) we can get that
E [F[(wT) F(w" < O
(n- m T log n +1 + +b-
SCSC: Similar to the stability proof of SCGD except for 2 San, (wr)
(Vgzi, (w,, pmee,) Vgz., (10:)) Viz,, (14+1)
b
(gz., (wy + pml))) Ia., (wi) V2 fss, (v1+1) Vo (w)).
based on the update of SCSC, we have that, for t/e S 2pt Tp P (4 + MyLs).
EA uT -way |] S
Ly My log(eT)
(28)
Pum
and
Ly [eTMgeTT) log(eT)
EA || pr 1.2
(29)
pum
Similar to the optimization proof of SCGD, also have that
E [[Fs(WT)
(s(w()))]
dL3
2 (eTg(eT)
L2L3 / 2d log(eT)
d2
- 4(d (6)
pPaaTT 1) + pa
+
paa(T 1) +
(30)
pa
where d1 = d - 1, d2 = d - (2p + 1) + (p + 2)²² Combining Theorem
Equations
and
30
can get that
E [[F(w)) F(w*)) ) s <0 (nn m m= T log T + + 12 + b b-
Proof of Corollary 2
SCGD: 1) EA
WT w
Firstly, when is * i, there holds
2
Wi+1 W++1
Wy w. 1/2 Vzz, (w:) (1241) + m V (w) Szz, (ub41))
36

---

+ n² uft"l]"
Agen ( (Vc+1) Vgas, ( (0141) ||
we
2076 ( (ur- w Vgzu, (wi) V fzye (u(+1) Vgz., (wf ) f3ze (o
|ere ws
fi2 =1 + T/1
(Jzz, (Ue+1 + pmnee) S3y, (Vc+1))
b
Wel
(ge., (we + pm - 9 (w²))
1
Wedl
fEg (uif1 + puree) - fzz (eff1)
P
62
1=1
1=1
12
1 b
Σ Uel
(gx, (wt + pu)))) g (cofit)
und
-
27%
Wt
62
(Ezs (1e+1 + paes) Szze (v++1))
Ued
(Jei, (wr + pmee)) - gzin (wx))
1=1
b
1 Ued (Fe, + para)) fey, (1ff1)
Uel (gey, (ub + prre.) - Ia. (wott))
With Assumption
3 the terms f(er+1) and g(we) are both differentiable.
Thus,
S Σ "id (f(e++1 + pou,i) - f(e(+1)) Eis the (g(we + pmme)) - g(we)) is also differentiable.
It is reasonable to assume that there exists primitive function f(ws) at least whose derivative undi
function is &2 Ei= una (f(1441 + pmme) f(v441)) Ei= P (g(w: pmue) g(w.)). Then P
W/ 1 - wi+1
We w 1|² 1|2
+ n Viz (wre ) Viz,, (wbtt)/ )|
21tt (we w/ V Ven (we) - V
Vfau frn, B3 (w))e)
(31)
Taking derivative of Vf V,,,,,,,
E3, (we) over we, we get that
2
S2n11, 1,, (w²)
b
Uel1
Vgnn (we) (V fey, (1e41 + ume,,) - Vaan (v++1))
Σ
Wed
(ges, (wr + pu),))) - gos, (wz))
12
1
Wnd (Jzg (Ve+1 + pule)) Sz,, (ve+1))
Σ
Well
(V (we + pmme.) Vgzc, (wx))
1
P
1=1
Thus,
f 23 2, (wz)
Ue. Vgzn (w:) (VSs,, (1141 + pme,)) V V52n (Me41))
Σ
Wed
(gos, (we + pm0),)) Iei, (w.)
Usd (fzz (1e+1 + pmr,)) - f2,, (ve+1))
Σ
We.1
(Vgz,,
(we, + pran.) - Vgzi, (wi))
1=1
3
Med
Izs, (wx) (Vis, (ve+1 mwex) V, (ve+1))
Σ
Ued (9z2, (wo + (mle)) Ies, (wi))
1
1=/ 1
+
Ut.! (Jzy (We+1 + +lree) SEy, (We+1))
Uell Σ
(Vgza, (we + pmne,) -gz (wi))
1=1
1=1
37

---

1
S n12 (BLgWfM + M))
M,),) then San,z, (wx) is p-smooth. And we can know that Let P # (BIgM3M MM,M)
Amin (2 2 2-
-- V (wce) 2 -p. According Lemma 3 can get that
W - wh.
Vizz En (we) Vinn (u)²()
2011
(1-2)
PT]
1:3 V V (wx) Vfey En (u 2.2 /|@ p
w 4.3 Vfnn B3 (wx) + Vf &, (uf ||?
2
-21
(1-
PT]
/ (wx) Viac (uy i,z ||
Wx+1 w/+1
1
2
Now, plugging the above inequality back into Equation
yields
W
w2+1
1.2 W/
w
+
nn² 4n² (1 pT) |Wee1
V 23 (w, VT (wt²))
+ +ppm
|c+t w
wi" 1 W/
2
2pm
1.2 wi+1
|
where the second inequality is due to 17t S 2pt
The above inequality implies
2p'
W1+1 w S VI - 2pm
|ws w
Secondly, when i = i, there holds
1.2
W++1
w
W 1.
me V ge., (w)) V fa,, (u(+1) 17s Vgzt ( fe, (o/41)
V gzz, (w)) V (u2+1) Vozi, (w ( V (,
10
w
7/
Wr
w/?
+ 2nc
Vgz., (wx)) (1,,,))))4))
2M, M m
w
+
112
Combining the above two cases, we can get that
[we41 VT- 2pm
1
w. w
llue + 4]
(1u
w/t/
2M, Mg 412
me
llie i].
Taking expectation over is.
E2
1.2 wx+1
(1100 wf
2M, Mg 112 mi
W/ w/ 3.2
E, [l * e]] +
Ex [[[ {]]
V1
2pT
2M M4
We w
V1
2pm
Then, taking expectation over and taking summation from / to T to get that
EA
WT
wh
1
EA
diz WT
wT-1
2.M Mg 12
m
V1
2pth
T-1
1
2M M p2n
M
m
VI
2pm
(P=t+1
38

---

M
1'
1
My 1
8 8-11
ppPn
T-1
M
exp
pu²2 t
1==2
T-1
1
M
cxp
t'
pn²2
M, ( & log(eT)
(32)
pu2n
where the fourth inequality is from et 2 +1+22 x.
2) EA
WT
1.2
: Firstly, when je # j. there holds
WM+1 w/+1 2
(1/41) I²
W/ w/" 1 - T/t Vzz, (w;) fzz, (v++1) + n) Ve,,
W w || + n gs., (we) V.z, (uc+1) & (wi ) (oft1)
( We wpt Vez (we) V fzy (M(+1) Vizz, (w² / fz, (
21%
b
We wt w
2
2
Wr.1 (Jz,, (Ue+1 + pmm.) SzY, (W++1))
+
1=1
Vdd
(we + p)),,) I2s, (wi) (92z,
Well
(Jzy (vfif + -uue)) - Szy (v/11)
11
1m1
6
b
Σ
(9,,, (wt 2 + (ue.)) gase (wopit)
2mp
Wi
wh
Ur
6²
1m1
(Uaja (ve41 + +uur))) Say (1)+1)) E Vell (gau, (we + puve,) - gzs, (wi)
b
Wes
(JEy (1bii + +wr,,) San (1241)
Σ We, 1=1 1
(9zy, (wt + pman.) - I2n, (wr
12
1=1
With Assumption
3 the terms (((++))) and g(wre) are both differentiable. Thus, (s(ws + pwn,)) - g(w:)) is also differentiable.
1
Σ Wid "
(f(14+1+ (ww,)) - (()++)) Ei= whe
a It is reasonable to assume that there exists primitive function f(wx) at least whose derivative oid P (g(w, pue,s) g(w.)). Then
8
function is 1 Ei P
6 Mis (f(1441 + (ue,)) f(0(41) Et
2
Wz+1 - w
Vizn, (wr) I2,, (wf/:)) )
+ nh
21/e (wr - w/ 5 v S2n, (we) - V Sea, 22 (wl):))
(33)
Taking derivative of Vf f2, (w:) over w., we get that
V2 fe (w))
39

---

Vt.l
Von. (we) (Vis, (v++1 + pree,)) - Vfzz, (v(+1)) Σ
Hed
(gzu, (we + puv),)) - gos, (wz))
12
1=1
1=1
+ 8
1
Uhd (Sz (1e+1 + +wms)) Szz, (0++1))
Σ
vel
(Vgzn, (wi + pove.) - Vgzi, (we+)
1=1
1=1
Thus,
4 E. F,. (wi)
b
Wr. gzz, (wz) (V fzz, (1++1 + pm VJEz (v++1))
Ued
(gzz, (wi + pmue.)) - I2s, (wx))
6
1=1
Ued
(fz, (ec+1 + puaee)) fsn (v(+1)) Σ
Well
(Vgz,,
(we + pove,))
Vgrn, (wi))
<
8
Ut
Vaz.. (wiz) (V (ve+1 + mwnee) VSzga (vz+1))
Σ
b
Usd (gen, (wr + mme, Jase (wee))
2
J
1=1
+
uhd (Jæz (Ue+1 + pulee) fEn (U(+1))
Σ
Well
(Vgz,, (we + pwee)) Vggs,, (wi))
62
P
1m1 P
<
(BL Mg + M,)
112
Let p = #/2 M3L + +, then fan, (wx) is p-smooth. And we can know that
Amin (z 2 - V (ws) 2 p. According to Lemma 3 we can get that
W/ w Vfzu (w:) Vzzuz, (w)-))
2011 (1
pT)t)
V e, (w:) Vfen En (wzf.) ||?
w. 1.5
Vfen s, (wx) + Vie, &, (wct.))
p
Wt
2
-21
(1
PT)
|[ (w:) Vence (w/+
1.3 s|?
Wi+1
3.3 w++11
2
Now, plugging the above inequality back into Equation 33
yields
Wc+1 - i+1
W/ mrg
4n7 (1
pM)
)
V ai (w, en, (wtt+) + 2pme | w(++1
2
W1411 w 2
We wft
+ 2pm
where the second inequality is due to 1/+ S
S 2p"
The above inequality implies
2pt
WM+1 w4th 5 VI - 2pp
Wc w.
1.8
Secondly, when ji j. there holds
1.2 Wc+1
w
ms 9z.. (we) VTz, (1++1) + 176 Vgz, (w/ 1 (01+1
W/
w
W/ w
V 9z., (w:) V fzy (1++1) Vgz., (w. 1 V (o/+a
+ 1/
W/
w.
+ 2m
4gz, (wm
65 (v1+1)
40

---

2M, y Mg
w up
T).-
Combining the above two cases, get that
We wt Hii + + (1 -
2M Mo
[1+41 - w v1 2pm
wp
+
11i = 51.
1²
Taking expectation over dz.
Ei
1.2 |uu41
w/-1
(1w)- wp.3
,M,
M,, n1
W1 w
Bi, [L + j]l +
Bi, [L j]l
I
2pT
4
1
W4 wt
1
2M Mg
nt.
2pT
pmmm
Then, taking expectation over A and taking summation from / = 10 T - to get that
EA
WT
1
EA
WT
w/
2M Ma 1.2m
2pm
T-1
1
2M, Mg
p.m n/
V1
2pmr
1
M, 1
1
pm12m
M, 1
pn2m t
T-1
M,
exp
pp2m
T-11
1
My
Σ
exp
pu2m
My MyMy(eT) 3 log(eT)
(34)
pp2m
where the fourth inequality is from ex 21+2
As for the optimization analysis of the full black-box SCGD, we can combine the proof' of Theorem and Corollary I to get that
E [Fs(w)r) Fs(((S)) < O (n* + dg + dz)
(35)
where d2 = - 2 (p + 1)) 3 + (p + 2) B. Combining Theorem Equations 32
34 and (35)
can get that
E [F((T) F(w")) ) s (n- + m -
Tb log T + n + nx + b 2 + b=
SCSC: Similar to the proof of SCGD except for
2 fayee, (w))
Hal Vysa, (wi) (V [V,,, (Ve41 + pmue)) - VS (w(+1)) Σ
Well (gzn, (we + pmae,)) - Izc, (wi))
12
1=1
+
Und (fz, (we+1 + puae))) fsy, (1++1))
Σ
We,1
(V (we + paae.)) Vazu, (we)):
r
41

---

based on the update of SCSC, we have that, for 1/2 5 2pt S 2p-
(IgM,, + My
My log(eT)
E
1. wT
(36)
pp2n
and
My Mg log(e)
EA
WT
wf
(37)
pp²m
As for the optimization analysis of the full black-box SCGD, we can combine the proofs of Theorem Hand Corollary
4
| to get that
E [Fs (WT) Fs(w(S)) o (n* + +b
(38)
where d2 can get that
2 (p + 1) (p + 2)) Combining Theorem Equations (36). 437 and (38).
E E[ F(w")] =0(m)) (n-1+m=1) (n((n++++) T log T + + p² + 2 bb
E Proofs of Applications
Before stating our remain proofs. should be noted that there a few differences between the setting of FOO-based VFL (VFL-CZOFO) and the one of SCGD (SCSC). First of all, we set S {ž1,... 2n and St.= { ..., 2 </, Ri+1, ... 2n according to the learning paradigm of VFL. Secondly, the update of the outer model (global model) for FOO-based VFL (VFL-CZOFO) is not based on the simple weighted summation of SCGD (SCSC). Luckily, these differences will not make a difference in our proofs.
Proof of Corollary
FOO-based VFL: Considering the independence of all clients, just prove the corresponding result of the k-th client for some l E [K]. Firstly, when is & i, there holds
k i.k 2 1+1
w/+1
w/ - T) V V (VV
1 w. 1/ + n Vg( Vg(wtV/((((u)) Vg(u Vu
27 " - - Vg(w Vg(w()) - Vo(u; [g
where wi w.... is simplified as wi With Assumption the terms Vg(uf) and V (g((w()) are both differentiable. Thus, Vg(w() V (g(w()) is also differentiable, which means that it continuous on its domain. As we all know, a continuous function has primitive functions. Then, it is reasonable assume that there exists primitive function fww() at least whose derivative function Vf(wf) V "o(w?) V (g(ww)) For example, considering the independence between e and g( ), f(((w() one of the primitive functions fww Then
w - w
w
wi 1 ||2 + mi
v Vf 2m (wt wit vf(w() vf(u(tt) (39)
Taking derivative of ( over wt. we get that
v'((w²)) V2g(wt) V
( v(g(())))
42

---

Thus,
v2 S (wr))
I agLs Lz
Let P =agbs- + Lzas then f(of)) is p-smooth. And we can know that Amin (ves(utt) 2
V2 f(w( 2 -p. According to Lemma 3 we can get that
w wi
Vf(w)t) v (mett))
221
(1
mile
Vi(w(t) Vi(ut )
) || P Iuu -wihh - vs(w,)) + 4 Vi(ug 12
2
-211
(1
MT]
v((ut || p o wi+1
t.k
2
Now, plugging the above inequality back into Equation 39
yields
2.k | 1.k
W 1+1
1++
W/
u
2
(1z² -1/² (1- pT:) ))
V Vf(wt) 2pm
|
i.k 1|2 wi+1
w/
k
w.
ppm
/ -
wi+1
2.k:
where the second inequality is due to 17t
1
3
The above inequality implies
2pt
2p"
[ w w
5
w
wi
1
VI 2pm
Secondly, when it = i, there holds
w with
w wy
k
17t V/oo ((ll
wx w/
+ 17t (g Vg( Vo(ut+)
w
w
+ 2m [
VA
w
wi k.
+ 2L Ly.
Combining the above cases, we get that
[ - wifh VI- 2pm
w wi d.k
llee + i] + (lloft - wfth +LLgLmm llle t).
Taking expectation over is.
E;
k /1
1+1
w++1
E., [ie + i]] + (1lu with +T..g.,.1e E,, [T(ee i]]
< 2pmp
2 2T Tog n
w.""
VI
2pm
Then, taking expectation over A and taking summation from t to to get that
1
2L Ls 1/
E
k WT
wT
f.b
EA
WT
WT 1.k
V1
2pT
72
1
2T T.g qe
VI
2pmp
n
P=t+1
43

---

1
Lgbg
1
pn
P=t+1
1
TzgTs 1
pn t
2'=2
T-1
T
exp
1'
pm t
T-1
S
cxp
t'
pm
1 (e log(eT)
(40)
pn
where the fourth inequality is from e² 2 1 x. Combining Theorem 3 and Equation get that
40 we
E [[F(W) Fs Es(w O (n (n-1 2 log
Proof of Corollary Corollary
5 Similar to the proofs of Theorem and Corollary we can get the result of
F
Key Challenges and Technical Tools
In this section, the key challenges and technical tools of extending the theoretical analysis for SCO problems from white-box cases to black-box cases are listed as follows.
Considering three different types of black-box SCO methods, we apply our new non-convex analysis (Theorem 3) to these cases (Theorem 4 Corollary and 2 in Section 3.2 Due to the difference related to function form, there are some differences related to the upper bounds of first-order and -econd-order gradients of f between Theorem and the generalization part of Theorem The differences among Theorem and Corollary Corollary are the same as Theorem
(1) Generalization:
(2) Optimization: For optimization, the estimated gradient does introduce several extra terms regarding the accuracy of the gradient estimation, i.e., V (p + 1/2)8V and V fV These terms are derived from some special strategies (such special decomposition V V (p + f (p 1/2) f). We propose extended lemma (Lemma 6 from [39 and combine this lemma with these strategies to limit the expansion of (w:+)((+)))) - [s(w(S)) during the iterations. Otherwise, these extra terms will lead to the divergence of our result.
Finally, we want to emphasize our advantages compared with previous work related the generaliza- tion guarantee of SCO (21).
(1) Better results:
For convex optimization, Theorem 2 leverages the co-coercivity property of
convex and smooth function to provide the stability bound O(nn~ + m m-1),3 log 7) under milder parameter selection than 21 And our proof is more concise since it avoids the intermediate step which measures the distance between e and g(w) in the analysis of (1
(2) Non-convex guarantee: We leverage special lemma, almost co-coercivity lemma, to develop proof framework to non-convex case obtain the first stability bound O( + m -')T log T) under milder parameter selection than 339
NeurIPS Paper Checklist
1. Claims
44

---

Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The paper's contributions and scope can be found at the end of the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [No]
Justification: Despite the limitation isn't discussed in separate "Limitations" section, some remarks of results have demonstrated the limitation. For example, Remark 4 shows that Theorem is looser than Theorem Remark shows that Theorem is derived from more stringent condition, i.e., smaller learning rate.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
45

---

Justification:
The full set of assumption and a complete (and correct) proof are provided in the Section 2 and Appendices
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper's contributions are from the theoretical analysis perspective.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
46

---

Answer: [NA]
Justification: The paper's contributions are from the theoretical analysis perspective. There isn't 't any data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips. //nips.cc/ppl cc/public/guu /etggudddsse/eebbbinninn htt.SSbbbiiiiooooiiiii.oooi for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper's contributions are from the theoretical analysis perspective.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[NA]
Justification:
The paper's contributions are from the theoretical analysis perspective.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
47

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper's contributions are from the theoretical analysis perspective.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/neurrpp: http:///weurip.cccciieee httppbbiic/tthhccuuuuuieoooooodd
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper's contributions are from the theoretical analysis perspective. theoretically explains the impact of black-box on the learning guarantees of SCO algorithms, which may benefit the algorithm designing of SCO algorithm.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
48

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper's contributions are from the theoretical analysis perspective without any data or model being released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper's contributions are from the theoretical analysis perspective. The algorithms analyzed in the paper have been cited properly.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
49

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper's contributions are from the theoretical analysis perspective without any new assets being released.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper's contributions are from the theoretical analysis perspective.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper's contributions are from the theoretical analysis perspective.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
50


Reviews:
[{"review_id": "X4dkp49NzY", "reviewer": "Reviewer_Xsnq", "summary": "This paper studies stability-based generalization bound for SCGD and SCSC, as well as the convergence rated of their black-box variants. The authors provide sharper generalization bounds for these algorithms, and the first convergence bounds for the black-box variants of these algorithms under PL-conditions.", "questions": "Please see above.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Strengths:\n\n1. **Novelty of the Problem**: The generalization bounds of stochastic optimization algorithms have been previously studied (e.g., [21]), and basic mathematical tools (algorithm stability) for such studies have been proposed. This paper is the first to study block-box SCSC. Although from the proofs of Theorems 3 and 4, the analyses for SCGD and SCSC are essentially the same.\n\n2. **Significance of the Results**: \n   - **Generalization Bound**: The authors provide a generalization bound of \\(O((1/n + 1/m)\\log T + 1/\\sqrt{n})\\) for SCGD and SCSC, which is significantly sharper than the previous \\(O(1/n + 1/m)\\log T + 1/\\sqrt{n})\\) bound. This is a noteworthy contribution.\n   - **Algorithm Convergence**: The paper presents convergence bounds for algorithms using estimated (black-box) gradients. While the dependence on \\(T\\), \\(n\\), and \\(m\\) is similar to [21], there are additional terms related to the estimation distance mu and sample size b. Moreover, the authors proved this results under a milder condtion (convexity vs PL-condtion. )\n\nThere is no experiments in this paper. However, the main goal of this paper is to study the properties of existing algorithms, so experiments are not necessary. But in the remarks the authors say that their theorem provide a more \"practical choise\" for paratmeres, so experiments might still be helpful to demonstrate this. \n\n### Weaknesses/Questions:\n\n1. **Comparing Convergence Rates**: In Table 2, it is difficult to compare the convergence rate of the proposed algorithm with other methods. The theoretical results of other methods are provided with respect to \\(T\\), but for the proposed methods, the dependence is given with respect to \\(\\mu\\) and \\(d\\). This inconsistency makes the table unclear. For instance, Theorem 3.7 of [21] also provides a way to configure \\(T\\). It should be made more clear that mu and b are extra terms.\n   - **Parameter \\(\\mu\\)**: The parameter \\(\\mu\\) is mentioned only once in Line 112, and it is unclear how good the \\(O(\\mu^2)\\) bound is. It seems that \\(\\mu\\) is used in the estimation of the gradient and is a constant. Therefore, Theorem 4 suggests that even if \\(n\\), \\(m\\) and \\(b\\) approach infinity, the difference between function values will converge to a constant instead of zero.\n\n2. **Redundancy in Proofs**: In the appendix, the proofs of Theorems 3 and 4 appear nearly identical (at least for parts 1) and 2)), with the main difference being the use of the estimated gradient. Additionally, the proof of Corollary 1 repeats similar arguments. I encourage the authors to reduce redundancy, shorten the proofs, and highlight the main differences to enhance readability.\n\n3. **Challenges of Estimated Gradient**: The current form of the proofs makes it difficult to tell the main challenges of introducing the estimated gradient in Theorem 4 compared to Theorem 3. From Lines 546-547, it seems the estimated gradient only introduces several extra terms regarding the accuracy of the gradient estimation, which appears to be standard. Clarifying the main challenges and differences would improve the paper.", "weaknesses": "Please see above.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to you for your valuable comments and constructive suggestions. \n\n**Q1:** experiments might still be helpful\n\n**A1:** Thanks for your constructive comment. We also think some experiments might still be helpful to demonstrate our more practical parameter selections than [1]. There are some experiments [2-5] to validate the statement in line 188.\n\n**1) For T:** [1] provided some generalization bounds for convex SCGD and SCSC with some impractical $T$ such as $T=O(\\max(n^{7/2},m^{7/2}))$ in Theorem 4. While our convex result (Theorem 2) and non-convex result (Theorem 3) can achieve similar rates even taking $T=O(\\max(n,m))$ which better matches some empirical observations (Figures 1, 2 in [2], Figures 2 in [3], and Figures 2, 3 in [6]).\n\n**2) For $\\eta_t$:** Theorem 4 [1] took $\\eta_t=T^{-6/7}$ which is too small when $T$ is large. While our Theorem 2 takes $\\eta_t=O(t^{-1})$ closer to some empirical selections ($\\eta_t=O(t^{-3/4})$ [2,3] and $\\eta_t=O(t^{-1})$ [4,5]).\n\n**3) For $\\beta_t$:** Theorem 4 [1] took $\\beta_t=T^{-4/7}$ which is also too small since [2,3,5] empirically select $\\beta_t=t^{-1/2}$ or $\\beta_t=t^{-1}$. In contrast, our theorems have no special restriction on $\\beta_t$. \n\nWe have supplemented these explanations in Remark 3 of our new manuscript to benefit readers’ understanding. \n\n[1] M. Yang, et al. Stability and generalization of stochastic compositional gradient descent algorithms. 2023.\n\n[2] T. Chen, et al. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. TSP, 2021.\n\n[3] M. Wang, et al. Stochastic compositional gradient descent: Algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 2017.\n\n[4] Z. Huo, et al. Accelerated method for stochastic composition optimization with nonsmooth regularization. AAAI, 2018.\n\n[5] J. Zhang et al. A stochastic composite gradient method with incremental variance reduction. NeurIPS, 2019.\n***\n**Q2:** how good the O(\\mu^2) bound\n\n**A2:** We first explain the parameters $\\mu$ and $d$ again.\n\n**1) For $\\mu$:** Eq. (4) estimates the unknown gradient by the standard finite difference method, where $\\mu$ denotes the approximation distance between two model parameters $v+\\mu u$ and $v$. The closer the approximation distance, the more accurate the gradient estimation. \n\n**2) For $b$:** The parameter $b$ denotes the number of approximation directions. The more approximation directions, the more accurate the gradient estimation.\n\nIn a word, our convergence rates depend on the quality of gradient estimation measured by the two parameters $\\mu$ and $b$. Next, we will compare our convergence rates with other rates.\n\nExcept for providing the generalization guarantees of (black-box) SCO methods, our main aim is to theoretically show the intuition that the more accurate the gradient estimation, the better the convergence rate. For the comparisons in Table 2, we have supplemented the selection of $\\mu$ and $b$ in the remarks (Section 3.2) of our new manuscript to achieve the similar convergence rates to [1-3]. For example, to obtain a convergence rate $O(T^{-1/4})$ similar to [3], we can select $\\mu=O(T^{-1/8}),b=O(T^{1/4}d_2)$. $\\mu$ can even be taken as a smaller value such as $0.0001$ in [6]. Therefore, $\\mu=O(T^{-1/8})$ is reasonable. And, although $b=O(T^{1/4}d_2)$ may be so large that the time complexity of model training is increased, this work aims to first show that black-box SCO algorithm can converge and its impact factors, rather than obtaining an optimal convergence rate.\n\nBy selecting the above specific $\\mu, b$, we have modified our results in Table 2 to make the comparisons more clear.\n\n[6] P. Chen, et al. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. AISec@CCS, 2017.\n***\n**Q3:** Redundancy in Proofs\n\n**A3:** We have simplified our proofs in our new manuscript to enhance readability. For example, we have omitted the part using Lemma 3 in the proof of Theorem 4. To further clear these differences, we have added a table (in “Author Rebuttal”) at the head of Appendix C.\n***\n**Q4:** Challenges of Estimated Gradient\n\n**A4:** We will emphasize the main challenges of introducing the estimated gradient as follows.\n\n**1) Optimization:** Lines 546-547 are related to our optimization part. For optimization, the estimated gradient does introduce several extra terms, i.e., $\\tilde{\\nabla} f-(p+1/2)\\beta\\nabla f$ and $\\tilde{\\nabla} f-\\beta\\nabla f$. These terms are derived from some special strategies (such as a special decomposition to $\\tilde{\\nabla} f$ in the second equality of line 546). We propose Lemma 6 based on [7] and combine it with these strategies to limit the expansion (line 549) of $\\mathbb{E}[F_S(w_{t+1})-F_S(w(S))]$ to ensure the convergence of our result.\n\n**2) Generalization:** We apply our new non-convex analysis (Theorem 3) to three types of black-box SCO methods (Theorem 4, Corollaries 1 and 2). Different function forms lead to some differences related to the first-order and second-order gradients of $\\tilde{\\nabla} f$ (please see lines 513-518) between Theorem 3 and Theorem 4. The differences among Theorem 3 and Corollaries 1, 2 are the same as Theorem 4. Our new non-convex generalization analysis (Theorem 3) is developed from our new convex generalization analysis framework (Theorem 2) via replacing the co-coercivity property of convex, smooth function with the almost co-coercivity property of smooth function. Our analysis avoids the intermediate step measuring the distance between $v$ and $g(w)$ in [1], and gets better results $O((n^{-1}+m^{-1})\\log T+n^{-1/2})$ under milder parameter selection.\n\nWe have supplemented the above explanations in Section 3.2 of our new manuscript to benefit readers’ understanding.\n\n[7] J. Duchi, et al. Optimal rates for zero-order convex optimization: The power of two function evaluations. TIT, 2015.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zYlwSKoFwn", "reviewer": "Reviewer_e2GF", "summary": "This work presents the generalization upper bound for two stochastic compositional optimization methods, SCGD and SCSC, under convex and non-convex setting. For convex setting, the presented generalization bound is tighter compared to the existing work and it matches the generalization bound of SGD for optimization without compositional structure. For non-convex setting, this work establishes the first generalization bound in SCO literature. Furthermore, this work studies the zeroth-order extension of SCGD/SCSC and presents their excess risk bound in non-convex setting. This is also new in the literature.", "questions": "Please see the weakness section.", "limitations": "No significant limitations in this work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The main contribution of this work is the theoretical analysis as I summarized in the summary section. \n2. It is interesting to see how estimation distance $\\mu$ and the number of estimation directions $b$ affect the excess risk bound.\n3. This work is well-written and easy to follow.", "weaknesses": "I do not recognize any significant weakness in this work. But I do have some questions.\n\n1. In Table 1, I noticed that the assumption V (bounded variance) and M (bounded function) do appear in SCGD/SCSC (Thm. 2), but not in SGD ([26] Thm. 3.8). Based on my understanding, the assumptions on both of these two analysis are the Lipschitz and smoothness of the unbiased stochastic function values. I do not see any major difference between them. Can the authors clarify what V (bounded variance) and M (bounded function) stand for?\n\n2. In Table 2, the optimization bounds for the black-box methods seem to omit the terms involving $T,n,m$. This confuses me. Is there any reason that the $T,n,m$ terms are ignored here?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to you for your valuable comments and constructive suggestions.\n\n**Q1:** ...Can the authors clarify what V (bounded variance) and M (bounded function) stand for?\n\n**A1:** Thanks for your constructive comment. As you mentioned, Lipschitz and smoothness are both assumed in our Theorem 2 and Theorem 3.8 in [1]. These two assumptions are the most common conditions in learning theory.\n\nThe bounded variance assumption (**Assumption 2**) is also a classical condition [2-5]. It limits the ranges of the variance value of the given functions $g$. \n\nThe bounded function assumption (**Assumption 4**) is different from the traditional bounded function assumption $|f|\\leq M$. Assumption 4 requires the distance between two adjacent function outputs to be bounded, i.e., $$||g(w+\\mu u)-g(w)||\\leq M_g, |f(v+\\mu u)-f(v)|\\leq M_f,$$ which is milder than the traditional bounded function assumption $|f|\\leq M$. Besides, it also requires the distance between two adjacent gradient outputs to be bounded, i.e., $$||\\nabla g(w+\\mu u)-\\nabla g(w)||\\leq M_g^\\prime, ||\\nabla f(v+\\mu u)-\\nabla f(v)||\\leq M_f^\\prime,$$ which is milder than bounded gradient condition $||\\nabla f||\\leq L$ [1].\n\nThe above explanations have been added in the remark behind Assumption 2 and Remark 2. We hope our explanations can help you understand Assumptions 2 and 4.\n\n[1] M. Hardt, et al. Train faster, generalize better: Stability of stochastic gradient descent. ICML, 2016.\n\n[2] A. Nemirovski, et al. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-1609, 2009.\n\n[3] Y. Zhou, et al. Understanding generalization error of SGD in nonconvex optimization. Machine Learning, 111(1):345-375, 2022.\n\n[4] M. Wang, et al. Stochastic compositional gradient descent: Algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2):419-449, 2017.\n\n[5] T. Chen, et al. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. TSP, 69:4937-4948, 2021.\n***\n**Q2:** In Table 2, the optimization bounds for the black-box methods seem to omit the terms involving $T,n,m$. This confuses me. Is there any reason that the $T,n,m$ terms are ignored here?\n\n**A2:** In Table 2, we just show the main orders of our convergence results, and their corresponding complete form are shown at the end of every proof in our Appendix. For example, in line 552, the bound is $\\mathcal{O}\\left(\\mu^2(T^{-1}\\log T+1)+b^{-1}(d_1T^{-1}\\log T+d_2)\\right)$. Because the order of $T^{-1}\\log T$ is smaller than 1. Therefore, we just reserve $\\mu^2+b^{-1}b_2$. \n\nTo increase readability, we have modified our results in Table 2 to make the comparisons more clear by selecting the specific $\\mu, b$. For example, to obtain a convergence rate $\\mathcal{O}\\left(T^{-\\frac{1}{4}}\\right)$ similar to [4], we can select $\\mu=\\mathcal{O}\\left(T^{-\\frac{1}{8}}\\right), b=\\mathcal{O}\\left(T^{\\frac{1}{4}}d_2\\right)$. **For $\\mu$**, this parameter can even be taken as a smaller value such as $\\mu=0.0001$ in [6]. Therefore, $\\mu=\\mathcal{O}\\left(T^{-\\frac{1}{8}}\\right)$ is reasonable. **As for $b$**, although its value $\\mathcal{O}\\left(T^{\\frac{1}{4}}d_2\\right)$ may be so large that the time complexity of model training is increased, this work aims to first show that black-box SCO algorithm can converge and its impact factors, rather than obtaining an optimal convergence rate. The two extra parameters $\\mu, b$ do impact the convergence rate compared with the corresponding first-order methods.\n\n[6] P. Chen, et al. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. AISec@CCS, 2017.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dLNgMmi8U5", "reviewer": "Reviewer_NRWe", "summary": "In this paper, the authors systematically analyzed the generalization error and optimization error of the stochastic compositional optimization problems (for black-box cases).", "questions": "1. What is the key technical challenge of extending the theoretical analysis (stability analysis and optimization analysis) for stochastic compositional optimization problems from white-box cases to black-box cases?\n\n2.   What are the key technical tools employed to address the key challenge? \n\n3.  Is this assumption 5  too strong for non-convex analysis?", "limitations": "N.A.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and well-organized. \n\n\n2. The paper provides the generalization analysis and optimization analysis for stochastic compositional optimization problems in a systematic way.   The convergence rates for three different black-box cases are provided.", "weaknesses": "1. The technical challenge of extending the theoretical analysis (stability analysis and optimization analysis) for stochastic compositional optimization problems from white-box cases to black-box cases is not clearly discussed.  What are the key technical tools employed to address the key challenge?  It seems that the black-box gradient approximation in Eq.(5) satisfies the bounded variance assumption. So it is easy to plug this into the existing white-box analysis framework to achieve a generalization error and optimization convergence rate. What are the non-trivial techniques involved in improving the theoretical results compared with the previous work? \n\n\n2.  Assumption 5 for the non-convex analysis is weird.   Assumption 5 implies that any stationary point, i.e., $\\mathbb{E}[|| \\nabla F_S(w) ||^2]=0$, to be the global optimal point $w(S)$.    Is this assumption too strong for non-convex analysis? \n\n\nMinor:\n\nTypos:   Eq.(5) is a second-order approximation of Eq.(4),  \"=\" may be incorrect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to you for your valuable comments and constructive suggestions.\n\n**Q1:** What are the key challenges of extending the theoretical analysis for SCO problems from white-box cases to black-box cases? What are the technical tools employed to address these key challenges? What are the non-trivial techniques involved in improving the theoretical results compared with the previous work?\n\n**A1:** Thanks for your constructive comment. The key challenges and technical tools of extending the theoretical analysis for SCO problems from white-box cases to black-box cases are listed as follows.\n\n**1) Generalization:** Considering three different types of black-box SCO methods, we apply our new non-convex analysis (Theorem 3) to these cases (Theorem 4, Corollary 1 and 2) in Section 3.2. Due to the difference related to function form, there are some differences related to the upper bounds of first-order and second-order gradients of $\\tilde{\\nabla} f$ (please see lines 513-518) between Theorem 3 and the generalization part of Theorem 4. The differences among Theorem 3 and Corollary 1, Corollary 2 are the same as Theorem 4.\n\n**2) Optimization:** The lines 546-547 mentioned by you are related to our optimization part. For optimization, the estimated gradient does introduce several extra terms regarding the accuracy of the gradient estimation, i.e., $\\tilde{\\nabla} f-(p+1/2)\\beta\\nabla f$ and $\\tilde{\\nabla} f-\\beta\\nabla f$. These terms are derived from some special strategies (such as a special decomposition $\\tilde{\\nabla} f=\\tilde{\\nabla} f+(p+1/2)\\beta\\nabla f-(p+1/2)\\beta\\nabla f$ in the second equality of line 546). We propose an extended lemma (Lemma 6) from [1] and combine this lemma with these strategies to limit the expansion (line 549) of $\\mathbb{E}[F_S(w_{t+1})-F_S(w(S))]$ during the iterations. Otherwise, these extra terms will lead to the divergence of our result.\n\nFinally, we want to emphasize our advantages compared with previous work related to the generalization guarantee of SCO [2].\n\n**1) Better results:** For convex optimization, Theorem 2 leverages the co-coercivity property of convex and smooth function to provide the stability bound $\\mathcal{O}((n^{-1}+m^{-1})\\beta \\log T)$ under milder parameter selection than [2]. And our proof is more concise since it avoids the intermediate step which measures the distance between $v$ and $g(w)$ in the analysis of [2].\n\n**2) Non-convex guarantee:** We leverage a special lemma, almost co-coercivity lemma, to develop our proof framework to non-convex case to obtain the first stability bound $\\mathcal{O}((n^{-1}+m^{-1})T^{\\frac{1}{2}}\\log T)$ under milder parameter selection than [1].\n\nWe have supplemented the above explanations in Section 3.2 of our new manuscript to benefit readers’ understanding.\n\n[1] J. Duchi, et al. Optimal rates for zero-order convex optimization: The power of two function evaluations. TIT, 2015.\n\n[2] M. Yang, et al. Stability and generalization of stochastic compositional gradient descent algorithms. 2023.\n***\n**Q2:** ...Is Assumption 5 too strong for non-convex analysis?\n\n**A2:** Assumption 5 is called Polyak-Lojasiewicz (PL) condition, which is used extensively in non-convex optimization [3-5]. This assumption suggests that the function value gap $\\mathbb{E}[F_S(w)-F_S(w(S))]$ is dominated by the square of gradient norm [6]. It implies all empirical local optimal parameters are empirical global optimal parameters [7]. We use it to prepare for the characterization of $\\mathbb{E}[F_S(A(S)) − F_S(w(S))]$ instead of $\\mathbb{E}[||\\nabla F_S(A(S))||^2]$ [8]. We have added the above explanation behind Assumption 5 in our new manuscript. Besides, we have increased a section in the final part of Appendix to discuss this assumption in detail.\n\n[3] Y. Lei, et al. Generalization guarantee of SGD for pairwise learning. NeurIPS, 2021.\n\n[4] S. Reddi, et al. Stochastic variance reduction for nonconvex optimization. ICML, 2016.\n\n[5] D. Foster, et al. Uniform convergence of gradients for non-convex learning and optimization. NeurIPS, 2018.\n\n[6] Y. Bai, et al. On the complexity of finite-sum smooth optimization under the Polyak-Łojasiewicz condition. ICML, 2024.\n\n[7] H. Karimi, et al. Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition. ECML-PKDD, 2016.\n\n[8] A. Kuchibhotla and A. Chakrabortty. Moving beyond sub-Gaussianity in high-dimensional statistics: Applications in covariance estimation and linear regression. Information and Inference: A Journal of the IMA, 11(4):1389–1456, 06 2022.\n***\n**Q3:** Typos: Eq.(5) is a second-order approximation of Eq.(4), \"=\" may be incorrect.\n\n**A3:** Equation (5) is consistent with the forms of previous work [9,10]. The second-order term of Taylor expansion is regarded as the remaining item taking $v=v_{t+1}^*$ where $v_{t+1}^*$ is an unknown model parameter. We don’t need to know $v_{t+1}^*$. We have further explained it behind Equation (5) in our new manuscript.\n\n[9] K. Nikolakakis, et al. Black-box generalization: Stability of zeroth-order learning. NeurIPS, 2022.\n\n[10] J. Chen, et al. Fine-grained theoretical analysis of federated zeroth-order optimization. NeurIPS, 2023.\n***\n**Q4:** What is the key technical challenge of extending the theoretical analysis (stability analysis and optimization analysis) for stochastic compositional optimization problems from white-box cases to black-box cases? What are the key technical tools employed to address the key challenge?\n\n**A4:** This question is the same as **Q1**. Please see **A1**.\n***\n**Q5:** Is this assumption 5 too strong for non-convex analysis?\n\n**A5:** This question is the same as **Q2**. Please see **A2**.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thanks for the comments of all reviewers. Considering the limitation of character count, we provide the table of the main differences among our main results in "global response" and upload a PDF including this table. As mentioned in the **A3** (the Rebuttal to Reviewer Xsnq), we have added the table at the head of Appendix C in our new manuscript.

Table. The main differences among our main results. (Note that, these line numbers in this table are in our submission version.)
| | | | |
|:----:|:----:|:----:|:----:|
|**Results**|**Generalization**|**Optimization**|
|**Theorem 2**|**Co-coercivity (line 449)**|—|
|**Theorem 3**|**Almost co-coercivity (line 472)**|—|
|**Theorem 4**|**Unknown gradient estimation (lines 513-518)**|**Some decompositions to $\tilde{\nabla} f$ (line 546)**|
|**Corollary 1**|**Unknown gradient estimation (lines 563-568)**|**Some decompositions to $\tilde{\nabla} g$ (line 596)**|
|**Corollary 2**|**Unknown gradient estimation (lines 613-618)**|**Combination of Theorem 4 and Corollary 1**|
| | | | |

Meta-review: The paper studies stochastic composite optimization in the derivative-free setting. There are 3 main contributions: (1) sharpening and generalizing prior results on SCO algorithms SCGD based on an improved stability framework (2) developing guarantees for SCGD in the derivative-free and non-convex settings (3) applying the analysis framework to vertical federated learning (VFL) algorithms and obtaining generalization guarantees. 

Reviewers agree that the paper is clearly written and the theoretical results are comprehensive. Although several reviewers initially expressed concerns about the technical novelty of the black-box setting, the authors addressed these issues substantially in the rebuttal. In light of the general support from the reviewers, I recommend acceptance.
Decision: Accept (poster)