Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization
Authors: Zhuanghua Liu
Luo Luo
Bryan Kian Hsiang Low
Venue: NeurIPS 2024 poster (2024)
Keywords: compositional optimization; nonsmooth analysis
Primary area: optimization

Abstract: The stochastic compositional optimization (SCO) is popular in many real-world applications, including risk management, reinforcement learning, and meta-learning. However, most of the previous methods for SCO require the smoothness assumption on both the outer and inner functions, which limits their applications to a wider range of problems. In this paper, we study the SCO problem in that both the outer and inner functions are Lipschitz continuous but possibly nonconvex and nonsmooth. In particular, we propose gradient-free stochastic methods for finding the $(\delta, \epsilon)$-Goldstein stationary points of such problems with non-asymptotic convergence rates. Our results also lead to an improved convergence rate for the convex nonsmooth SCO problem. Furthermore, we conduct numerical experiments to demonstrate the effectiveness of the proposed methods.

Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization
Zhuanghua Liu
Department of Computer Science, National University of Singapore CNRS@CREATE LTD, Create Way, #08-01 CREATE Tower, Singapore 138602
Liuzhuanghua90gaill com
Luo Luo"
School Data Science, Fudan University
Shanghai Key Laboratory for Contemporary Applied Mathematics luoluo@fudan. edu.edu.uoo en
Bryan Kian Hsiang Low
Department of Computer Science, National University of Singapore 1owkh@comp. nus edu.
Abstract
Stochastic compositional optimization (SCO) problems are popular in many real- world applications, including risk management, reinforcement learning, and meta- learning. However, most of the previous methods for SCO require the smoothness assumption on both the outer and inner functions, which limits their applications to a wider range of problems. In this paper, we study the SCO problem that both the outer and inner functions are Lipschitz continuous but possibly nonconvex and nonsmooth. In particular, we propose gradient- free stochastic methods for finding the (6, G)GGoldstiin stationary points of such problems with non-asymptotic convergence rates. Our results also lead to an improved convergence rate for the convex nonsmooth SCO problem. Furthermore, to demonstrate the effectiveness of the proposed methods.
conduct numerical experiments
Introduction
In this paper, we consider the following stochastic compositional optimization (SCO) problem:
min (xx) f(((x)), XERd
(1)
where the outer and inner functions f: Th + TR and g: Rdd - R.m has the form of
f(y) A [F[F(y: (y: and
g(x) [G( ()],
and the stochastic components Fly: : { and G(x; () are Lipschitz continuous but possibly nonconvex and nonsmooth. Random variables and are independent. Such formulation is popular in many real- world applications, including risk management [I, statistical learning 22) reinforcement learning (3),
and model agnostic meta-learning
Most of the existing work 6 tion that both functions f(-) and g(.) are smooth. Unfortunately, many modern machine learning
for nonconvex SCO problem based on the assump-
The corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: We present the stochastic zeroth-order complexity of proposed algorithms for solving
nonsmooth stochastic compositional optimization problems.
METHODS
PROBLEM
COMPLEXITY
REFERENCE
GFCOM
NONCONVEX
0
COROLLARY 4.2
GFCOM
NONCONVEX
O 3 Old 24 4.8 + d2.58-2
COROLLARY 4.4
WS-GFCOM?
CONVEX
COROLLARY 5.3
WS-GFCOM*
CONVEX
O + 5 12:88-2-7 5)
COROLLARY 5.4
models including deep neural networks do not satisfy the smoothness condition. Ruszezynski 9 proposed a single time-scale stochastic subgradient method for solving the Problem (T). However, the author only provided asymptotic convergence analysis for the approach. In recent work. Liu and Davanloo Tajbakhsh 10), Hu et al. [11] presented the non-asymptotic convergence for the nonconvex nonsmooth SCO problem, while their analysis requires additional assumptions such as the weak-convexity and the relative smoothness condition.
The non-smoothness in the Problem implies the classical gradient-based approaches and the convergence measure in terms of the gradient norm cannot be applied. The Clarke subdifferential [2] for the Lipshitz continuous functions is a natural extension of gradients for the smooth functions. However, hard instances have shown that no deterministic or randomized algorithms can find an c- stationary point with respect to the Clarke subdifferential of a Lipschitz function in finite time [ 14). To address this issue, Zhang et al. [13] proposed a refined notion of the (ò, Golldsstni stationary point terms of the Goldstein 5-subdifferential, which considers the convex hull of the Clarke subdifferential at points in the š-neighbourhood [5]
In this paper, we propose zeroth-order stochastic method called gradient-free compositional op- timization method (GFCOM) for solving Problem (I) in finite time. In particular, we show that the GFCOM can find (6, -GGoldsttnni stationary point of the objective function (--) = (g()) within the stochastic zeroth-order oracle complexity of 8.5
Furthermore, we improve to establish a more effi- cient fisst-ordrr oracle estimator, leading to the algorithm GFCOM which achieves tighter upper complexity bound of Odd-58 -3e 35.5). In addition, we study convex nonsmooth SCO problems. In this regime, prior methods 2 12 21 suffer two major limitations: (i) Their convergence analysis based on the smoothness condition of the outer function. (ii) Their convergence result is mea- sured by the sub-optimality of the function value gap, while the non-asymptotic convergence rate for finding the stationary point has not been studied. We overcome these issues by involving a warm-start strategy into GFCOM*, which is guarantee to find (ő, e)-Goldstein stationary point within ( + 88.58 22 -2) stochastic zeroth-order oracle complexity. We summarize the complexity of proposed methods in Table
the GFCOM by using the variance reduction technique [1
Related Work
In this section, we review prior work for stochastic compositional optimization and classical noncon- vex nonsmooth optimization.
2.1 Stochastic Compositional Optimization
In a pioneer work, Wang et al. (2) studied the non-asymptotic convergence of nonconvex smooth stochastic compositional optimization by proposing the stochastic compositional gradient descent (SCGD), which contains two sequences of stepsizes for different time scales to update the variable and track the inner function value, respectively. The authors also heuristically extended their methods to zeroth-order optimization. Wang et al. [5] proposed an accelerated variant of SCGD using an scheme, and Ghadimi et al. (6] proposed a single time-scale approach to accelerate the convergence further. Additionally, Hu et al. 77. Lin et al. 220 Yuan et al. [22] incorporated the variance reduction technique into the first-order iteration, achieving a tight stochastic first-order complexity under the mean-squared smoothness assumption.
caappollatinsmmoothii

---

Compared with the smooth counterpart, the study of nonsmooth compositional optimization is relatively searce. Ruszezynski 99 proposed single time-scale stochastic subgradient method for nonconvex nonsmooth SCO problems, while the theoretical analysis only provided the asymptotic convergence rate. Liu and Davanloo Tajbakhsh
[0] introduced the stochastic composition Bregman gradient method and provided non-asymptotic convergence analysis under the relative smoothness condition. Vladarean et al. [23] proposed a Frank-Wole algorithm for constrained nonconvex nonsmooth SCO problems. Their analysis assumes that the outer function is convex but possibly non-differentiable, and the inner function smooth. Very recently, Hu et al. [ studied stochastic methods for the finite-sum coupled compositional optimization problem. Their convergence rate is established by assuming both the outer and inner functions are weakly convex, and the outer function is non-decre..ing. In addition, Kalogerias and Powell (44 studied the zeroth-order stochastic optimization for a specific compositional optimization problem in risk-aware learning.
2.2 Non-Asymptotic convergence Analysis of Nonconvex Nonsmooth Optimization
In this subsection, we present literature review for classical nonconvex nonsmooth optimization. The study of this field has a long history 12 25 but the non-asymptotic convergence analysis of nonsmooth optimization has only emerged in recent years. Zhang et al. [3] provided the non- asymptotic complexity analysis of the interpolated normalized gradient descent method to achieve (6, -oGoddsttinn stationary point of Lipschitz function with nonstandard subgradient oracle. Davis et al. 226. Tian et al. (77 improved this method by introducing random perturbations each iteration remove the assumptions. Recently, Cutkosky al. [28) proposed the optimal algorithm via the reduction from nonconvex nonsmooth optimization to online learning.
The development of non-asymptotic convergence analysis of zeroth-order methods for nonsmooth optimization was initiated by Nesterov and Spokoiny (29]. Later, Lin et al. (30] proposed gradient- free methods for this problem by establishing relationship between the Goldstein 6-subdifferential
and randomized smoothing. Chen et al. BI. Liu et al. [32
improved their results by leveraging the
technique. Kornowski and Shamir
33
obtained sharper bound by applying
the reduction technique introduced by Cutkosky et al. 28 to the gradient-free setting. Liu et al.
34 Grimmer and Jia (35) further extends the methodology to the constrained setting. However, these methods do not apply to the nonconvex nonsmooth SCO Problem (T.
3
Preliminaries
In this section, we first present the notations and assumptions used in this paper, then introduce the convergence criteria for nonsmooth optimization and the randomized smoothing technique.
3.1 Notations and Assumptions
We use ||-|| to denote the Euclidean norm of vector. We define Bs(x) & {y E IR:;
lly -x|| S 8}
as the Euclidean ball centered at x E IRd with a radius >> O. We let conv(A) be the convex hull of the set A. For two given sets and B, we define A B their Cartesian product. In addition, denote f g the function composition such that (J g)( A f(g(x)).
Throughout this paper, we assume the objective function satisfies the following assumptions.
Assumption 3.1. We assume the stochastic component F(-,)) L5 (E)psshhshh for any given &. and the stochastic component G(-, Q) is Lg (C.C--iipchhitt for any given Ç. That is, it holds
F 3 F(y.E) & (E) ||x ---y- yll and [[G($t.) - Gly. C)1l < Lg(C) 1
for any x. E IRd and ÿ E R We also assume the Lipschitz parameters Lt(E) and Lg(C) have bounded second-onler moments such that Ee(L)(E)?) < G2 and Eç Ee[L, < G. for some constants G Gg > O.
Remark 3.2. We can verify that Assumption 3.1 implies the function f(-) is Gipssshh, and the function g(-) is Gg Lippschhi by Jensen's inequality.
Assumption 3.3. We assume that there exists constant as the upper bound on the variance of
the functions G(,, S), such that for any x E RRd, we have Bg [[[[(x () -(())]²] S og.

---

Assumption 3.4. We assume that the composite function ((-) A (fog(() is lower bounded such that क- inf infxer ((x) DC.
3.2 Convergence Criteria for Nonsmooth Functions
We introduce the definitions of the Clarke subdifferential and approximate Clarke stationary points. Definition 3.5 (Clarke [2). The Clarke subdifferential of Lipschitz, at point x is defined as (x) A conv (g =- limx, +x V((xx)) Furthermore, we call point an c-Clarke stationary point of f if holds that min [g]| g E (x(x)) S.
Zhang et al. [13, Kornowkk and Shamir [14] showed that no deterministic or randomized algorithm could find an e-Clarke stationary point in finite time. Consequently, Zhang et al. [13 considered refined notion of approximate stationary point in terms of the Goldstein é-subdifferential.
Definition 3.6 (Zhang et al. (13).. Given a f f: E R and 8 > 0, the Goldstein which the
6 6-subdifferential of f at point x E R defined as fxf(x) conv conv(UyeR,tss (x) convex hull of the Clarke subdifferential at the points in the 9-neighbourhood of x. Additionally, a point x E Red is called (5, 6) Goldstein stationary point of f(.) if it holds that min (llgl]] g E 0s (x)) S.
Recent work 13 26, 28 has shown that it is possible to find (ō, c)-Goldstein stationary point of
a nonsmooth problem without a composition structure in finite time. However, these theories are not applicable to nonsmooth SCO. In particular, we can infer from Rademacher's theorem and Assumption 3.1 that the composite function ((-) is differentiable almost everywhere. Let Q C IRd be the set on which & is differentiable, then i 2 is of measure zero. Recent work assumes they have access to the unbiased stochastic gradient estimator of the objective function for any x E Q. In our setting, the unbiased gradient estimator of the composite function &(x) is Jx(x: V) (xx):))) where To is the Jacobian matrix of the function Gi:; C). However, such an estimator is hard to obtain because the function value g(x) is an expectation.
3.3 Randomized Smoothing
The randomized smoothing is popular technique for nonsmooth analysis (36 and gradient-free optimization [29]. Concretely, given Lipschitz function f and a uniform distribution P on unit ball, we define its smoothed surrogate fx(x) Eu- x + 8u)], which has the following properties.
Lemma 3.7 (Lin et al. (30 Proposition 2.3]). Let fo (x) = Eu-pl [f + ōu]] where P is a uniform distribution a unit ball in fg-norm. Suppose the function is L-Lipschitz. then have (a) [ff(x)) fxx] 8L: (b) fo(-) is differentiable everywhere and L-Lipschitz with cLvdō d8 d -Lipschitz gradient, where is some positive constant; (c) ff(xx) E fx) for any E TRd..
Moreover, we consider the following unbiased gradient estimator of the smoothed surrogate func- tion f-))), which can be obtained from two function query oracle calls on points uniformly sampled from unit sphere [37].
Lemma 3.8 (Lin et al. 30 Lemma D.IJ). Let f(x) ExF((x {)) be a L-Lipschitz function We denote
ux 2 d (F Su; - F(x du; E))u,
25
where is uniformly sampled from distribution unit sphere in Rd space. Then, have Ef[(x;; u, E)] fs(xx) and El]][(x; < 16 2n...2
4 Algorithms for Nonconvex Nonsmooth SCO
In this section, we propose zeroth-order stochastic algorithms for solving the nonconvex nonsmooth SCO problem. We also provide non-asymptotic convergence analysis for the proposed methods.

---

Algorithm 1: GFCOM(X0, fo,,,bb,, b9)
for 1 = 0, 1.....,T do
Sample (Er,s; wr and (-.
Generate G(x, + dWe.ji Se,e) for every (1,3) E [bal [by].
Let = 1 Eielb, G(x+ + dwesi Sr,a)-
b,
Let Zt,) 5y Eve(ty) G(x:, ((xx--öwan -Wi.s St.).
Ve = 1
by Ej((b,) (F(y.,)En.)) P(zz.fiEi))))
Update X++1 = Xt 1/Ve.
end
Return: Xn. where is uniformly sampled from [T].
Algorithm 2: GFCOM 7, T, b, bg. bg 1/ m)
for t 0,I,...,
do
if' t mod m = 0 then
Sample (Er.i, wr and (Gri)
4
Generate G(x; I dwi,j (r,)) for every (1, E [byl [byl.
Let ytj = 1 Eie(ba) G(x+ + dwe,fi (..).
$
Let Zt,j by EiE(,,) G(x: - 8w St.)).
Let = by Eje(tr) 28 (F(ye.;: - F(z (izzi,iEn.i Eng))
else
Sample (Er,i, wri 1/1 and (Sri)
10
Generate G(x; + dWi,ji (i,)) and G(x-11 &weyi Ct,e) for every (i, E [K) [b]]
11
Yk, F EiEry) G(x: + &owis Sk.i) for E (1-1,4)
12
Let Zk.j = 1
1/2 EiERY) G(xx+ - -Jwesi for h E -t-
Let q
8y Σ EjEby9 28 (F F(zz,ji ( for l E {t 1,t).
Let V, qt 9t-1 Ve-1-
15
end
16
Update X = X T/Vt.
17
end
18
Return: XR where R is uniformly sampled from [7].
4.1
The Algorithms
In this subsection, we propose the gradient-free compositional optimization method (GFCOM) and its accelerated variant GFCOM'. We first introduce the main intuition of the GFCOM. Consider the following hypothetical zeroth-order gradient estimator
1 bf
d (F(o(x, + ow..)): - F(g(xx (:
Σ jE(br]
V
28
where by > the mini-batch size of the gradient estimator. By Lemma 3.8 the vector V, is an unbiased estimator of V (xx)).. Unfortunately, it is intractable obtain the function values g(x, + dwe,) because g(.) an expectation of stochastic component functions G(=:C). To remedy this issue, introduce auxiliary variables yt,j and žı, to approximate the inner function values g(x; + owe,)) and g(x; - 5wt,,). respectively. In particular, the vectors Yt,j and žt,5 are mini-batch function estimators defined follows
1 Σ
Σ G(x+ Swa,) G(x+ + (was;Sea) and 21.j = by :E(b,)
Yt.j = bg vE(b,)
(3)
5

---

where by > 0 is the mini- size of the function estimator. Accordingly, we use these two variables replace the function calls of g(.) the gradient estimator v, of Eq. (2) The complete procedure of the GFCOM is presented in Algorithm
For the GFCOM*, leverage the variance reduction technique approximate (x)s In particular, we consider the following hypothetical recursive gradient estimator
V = q: q + Vt-1,
where and Q mini-batch gradient estimator defined as follows.
d (F(g(xx + ow.,)): - F(g(xx - Sw.,):&.,)))..
Σ JE(K]]
qle
B
28
where 8 > O is the mini-batch size and l E (t 1, Compared with the mini-batch gradient esti-
mator (2) the recursive gradient estimator (4) has been shown to achieve a sharper complexity bound
in nonconvex optimization literature 17 18 3T. However, the gradient estimator is computationally
intractable due to the unknown function (-). Similar to the development of Algorithm | we define
yt. Z, to estimate the inner function values g(x, + &W.,)). We also introduce variables Yr-1+ Z to approximate the inner function values (xx; - oW.,) at the previous iteration. Then we define stochastic gradient estimators q, and qt-1 in terms of yr. Vt-1, 2t and -
1 Σ D'S
d (F(yn.) - F(ze5: (t,))) Et.)) W
28 JE(D
for k (1 1, We replace the minibatch gradient estimator q. and qr-1 in the recursive gradient estimator V, of Eq. 4 with the refined gradient estimators qr and q:-1. The complete procedure of GFCOM" is presented in Algorithm
4.2
Convergence Analysis
In this subsection, we consider the complexity analysis of the proposed algorithms introduced in Section 4.1 We assume that ((ro) x" < R. where Rt > 0 is some constant.
The following theorem shows the convergence rate of solving the Problem ① with the GFCOM method presented in Algorithm
Theorem 4.1. Under Assumption 3.1 and 3.4 running the GFCOM algorithm (Algorithm 7
with 17 (c( GoGGGGGVV where
is some constant, then the output x satisfies
(Gror
GGGgVaR ST
G.GyVa
dG3G' dC
E [ =
(5)
T
bf
82bg
Using Theorem 4.1 with the parameter setting
G,G,vaR 862
+ G3G.Vd
dG (
12G7008 8222
T =
by =
and by = θ
obtain the following oracle complexity result for Algorithm !
Corollary 4.2. Under Assumption 3./ 3.3 and 3.4 the GFCOM algorithm (Algorithm 7 requires at
most O (B3.5G5 G3 R8-33 + Go -66) stochastic zeroth-order function query calls
obtain (8, -olossteni stationary point of db
now consider the convergence analysis of GFCOM*. We will show that enjoys a sharper complexity bound due to the utilization of the recursive gradient estimator. The following theorem shows the convergence rate of solving Problem ( with the GFCOM (Algorithm 2).
After giving the complexity bound of GFCOM Corollary 4.2
Theorem 4.3. Under Assumption 3.7
rumning the GFCOM* algorithm (Algorithm)) and GGG then the output xR satisfies
with ( b, (dG Ggg
GV 8T
VaG? T
aG
d²G3008
RC900
[ =0
+
by
82b
826

---

Algorithm 3: WS-GFCOM(XX. No. To: 6..0 71, T, b, bg 8/, 0/ m)
Let X1 GFCOM(X;; Nu To, 1, b.b)).
Option I (WS-GFCOM²): X2 (FCOMM(1,)) 17, T, (r.b,bb)..
Option II (WS-GFCOM"): X2 = GFCOM (xI,OM(XI,7,1T b/,,b/y.. bg bg m).
Reeturn: X2.
Using Theorem 4.3
with the parameter setting
Gd
Va by=
dGG e²
GP 8²
T=
by by =
de2
2²
obtain the following oracle complexity result for Algorithm 2
Corollary 4.4. Under Assumption
3.7
3.3 and 3.4 the GFCOM* algorithm (Algorithm) 2 requires
most O (dd G R8- G - stochastic zeroth-order function query e) calls to obtain ) Goldstein stationary point of 4
For both Theorem and 4.3 we take e = 1 according to Lemma 8 of Duchi et al. 336
4.3 Discussion
In Algorithm only apply the variance reduction technique to the outer function f(-) to accelerate our algorithm. In contrast, existing methods [2 7 [2] for nonconvex smooth SCO also apply the technique the inner function estimator obtain an improved complexity bound. Here briefly discuss the cause that leads to such a difference. For smooth optimization, the main intuition of the variance reduction technique is to establish connection between the bound of the mean- square error term ES ||v, (>(x))) and the expected distance of iterates at successive iterations
E||xx x which diminishes asymptotically. In our algorithm, we exploit the randomized smoothing with perturbed iterates x; + dw,, approximate the gradient of the smoothed surrogate function (x.). If we apply the variance reduction to the inner function estimator, the mean- square error Billv. ( )) [[]] ] is bounded by the expected distance of the perturbed iterates at successive iterations [ X 5(Wi.j -w-1 which does vanish asymptotically.
5 Extensions to Convex Nonsmooth SCO
In this section, we extend the result in Section 4.1 to study the convex nonsmooth SCO problem. Firstly, we introduce an additional assumption as follows.
Assumption 5.1. We suppose the function f(x) is convex and non-decreasing. G(x;; C) is convex for any given Ç, and the solution set X arg minxeRe 4(x) is non-empty.
From this assumption and Section 3.2.4 by Boyd and Vandenberghe 38 we can deduce that +(x) is a convex function. We will show that stochastic algorithms obtain an improved convergence rate for the nonsmooth SCO problem with Assumption 5.1 To obtain a (6, Gooldsttn stationary point of the problem, we propose a two-phase gradient-Iree stochastic method called warm-started GFCOM (WS-GFCOM) in Algorithm 3 The intuition is that we use the GFCOM method to get sufficiently small sub-optimality find the stationary point in the second phase. We remark that using the GFCOM method for the first phase is justified by the observation that can achieve optimal convergence rate in terms of the sub-optimality of function value gap given the access to the exact function value 9xx) 39
the first phase, and then we apply the proposed methods in Section I
5.1 Convergence Analysis
In this subsection, we consider the complexity analysis of the proposed WS-GFCOM method, Let R & minxex- || - xoll- We characterize the convergence rate of the WS-GFCOM method for the convex nonsmooth SCO problem at the first phase with the following theorem.
7

---

Theorem 5.2. Under Assumption 3.7
3.3 and 5.7 running the WS-GFCOM algorithm (Algorithm 3) with parameters to G To = ( 2 R
2), 0g.0 = @ (00=)) and
8 G then the oulput x1 satisfies [x((x)) $- S p. In addition, the total zeroth- order stochastic oracle complexity is at most Cd
Theorem 5 implies that the initial suboptimality at the beginning of the second phase is bounded by P. Consequently, the total complexity of WS-GFCOM (Algorithm 3 with Option I) is bounded
by (dd)) G o p+ + d3 GOG 0 1365-36-0- + dB a 20 c0)) An appropriate choice of
p leads the following oracle complexity of Algorithm 3 with Option I.
Corollary 5.3. Under Assumption 3.1 3.3 and 5.1 the WS-GFCOM algorithm (Algorithum with Option 1) requires at most O GJ G2. of R2-88-244
+ +d o0 stochastic
zeroth-order function query calls to obtain a (6, e)-Goldstiin stationary point of 4.
With similar deduction, we can show that using the GFCOM* for the second phase obtain improved complexity bound. The following theorem shows the oracle complexity of Algorithm with Option II.
3.3 and 5.1 the WS-GFCOM- algorithm (Algorithm Corollary 5.4. Under Assumption 3.1
with Option II) requires at most ( d G
G Ru g
2- + d3. o stochastic
zeroth-order function query calls to obtain a (6, e) GGoldsttin stationary point of Φ.
Experiments
We compare the proposed methods GFCOM and GFCOM* with wefffe-woofoiizz. style zeroth-order baseline method 2 40 In particular, the baseline gradient estimator is defined as
Vi bj
Σ
28 (F(y Et,)) F(zz,,i :(,z));
jELby]
where Yt.j and ž are function estimators defined in Eq. (3. Et., and E, are independent random variables. We test all the methods on the nonconvex penatized risk-averse portfolio management problem and a reinforcement learning (RL) problem. We set å = 0.1 for the GFCOM and GFCOM* methods.
6.1 Nonconvex Penalized Portfolio Management
We consider the portfolio management problem with capped-L, regularizer [41]. Let x denote the investment quantity corresponding to N assets and r, EN denote the returns of N assets at timestamp f. We can formulate the portfolio management problem as the following nonsmooth compositional optimization problem
min XERN
Σ (1,
T Σ
(rx,x)
1 E(r,,))
(r,,))
-xx(),
(6)
where B(x) D> min | a} and X, a 0 are tunable hyperparameters.. Specifically, the inner function G(x; and outer function F'w;; () can be formulated as
G(x: E) = [........ ,N (rg,
and
F(w: () --(r w|N + ((rg, W(N) - Wx+1) 3(x).
Both random variables & and Ç uniformly sampled from (1...., T). We choose À = 10-5 and a = our experiments. The goal of the Problem (6) to maximize the return while controlling the variance of the portfolio.
We compare all the methods on different portfolio datasets formed on Size and Operating Profitabil- ity
For all algorithms, we tune the stepsize among {1 10-5, 5,3 3 10 ..... x 10 10-3,3 3,3 x 10
http::/mba. tuck
html

---

500
Kinter GFCOM
500
Kiefer
400
Klefer
400
GFCOM
GFCOM
400
GFCOM
GFCOM
300
3 200
200
200
100
100
Function
108
168
Function Calls
(a) Asia Pacific ex Japan OP
(b) Europe OP
(c) Global ex US OP
Kieter
Kieter
Klefer GFCOM
300
GFC
800
GFM
600
GFCOM
GFCOM
GFCOM
600
200
LOGs
Loss
100
200
200
1.0
168
Function
168
(c) Global OP
(f) Japan OP
(g) North America OP
Figure I: We present the loss vs. complexity on several portfolio management datasets. The plot of GFCOM and the Kiefer- Wolfowitz method are overlapped as their performance close to each other.
0.400
0.400
0.400
0.375
0.375
0.375
0.350
5 0.325
0.325
0.300
Kiefer
0.300
Kiefer
0.300
Kiefer
0.275
GFCOM
0.275
GFCOM
0.275
GFCOM
0.250
GFCOM
0.250
GFCOM
0.250
GRCOM
0.5
1.0
0.00
0.25
0.50
0.75
1.00
0.0
0.5
1.0
Function Calls
1e7
Function Calls
1e7
Function Calls
167
(a) 400
1l 600
(c) nl = 800
Figure 2: For the RL task, we present the loss complexity on datasets with states of different sizes.
We choose the mini-batch size by b, 1000. addition, we by 100, , 1000 and m / 10 for the GFCOM* algorithm. Figure shows that the GFČOM* algorithm converges much faster than the GFCOM and the baseline method across all datasets.
6.2 Application to Reinforcement Learning
We demonstrate an experiment on RL and verify the effectiveness of the proposed methods on value function evaluation. Let 4 (s) be the value function of state under policy for all state S where [S] = n. Let _s be the reward transition from s' to 8, and 7 > 0 is a discounting factor. linear map of some
Furthermore, assume that the value of each state can be parameterized feature map v/. E Rd of the state such that V*(s) = (tb,, w). Then we formulate the RL problem Bellman residual minimization problem
Σn
(Wi,, ( w)
Eas
Paw (ra + Thke, w/)
min WERd
where Pas is the probability transition matrix and h(x)) = 1-expp | /a) is nonconvex nonsmooth loss which is more robust to adversarial outliers than the squared loss 43 Specifically, the inner function G(x; E) and outer function F(w; () can be formulated as
G(w; Q) (( w),r1.s 7/ w)...., (kh, wn. + 7 w)]

---

and
(z 22(+1).
In the above formulation, each & is uniformly sampled from {Pa...., Pin] and C is uniformly
sampled from {I..... T. We follow a similar experiment setup by Yuan et al. [2 Specifically, we generate a Markov decision process with different numbers of states
{400, 600, 800} and 10
actions at each state. The transition probability matrix is generated from the uniform distribution
from [0, 1]. In addition, the rewards are sampled uniformly from [0, 11. In terms of hyperparameter setting, we choose by- = by = 100 for all algorithms. addition, we set b/ = 10, b/ 100 and m = /b = 10 for the GFCOM algorithm. For other hyperparameters, we use the same setting for the portfolio management problem. The experimental results in Figure Souure@stnnn show that the GFCOM* significantly outperforms other methods.
7 Conclusion
In this work, we propose novel zeroth-order algorithms for nonconvex nonsmooth stochastic compo- sitional optimization. We present the non-asymptotic convergence rate of the proposed algorithms for obtaining a (ő, e) G-Godsttiin point of the problem. Furthermore, we extend our methods with a warm- start phase to solve the convex nonsmooth SCO problem with improved convergence guarantees. We conduct numerical experiments on portfolio management and reinforcement learning problems to demonstrate the effectiveness of the proposed algorithms.
In future work, it is interesting to study the lower bound of the zeroth-order algorithms on nonconvex nonsmooth SCO. It is also interesting to investigate whether the complexity bound of zeroth-order algorithms can be further improved.
Acknowledgement
This research/project is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: SSGG2-PDD-2003--8-0033777 This research part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister's Office, Singapore under Campus for Research Excellence and Technological Enterprise (CREATE) programme. Luo Luo is supported by National Natural Science Foundation of China (No. 62206058), Shanghai Sailing Program (22YFI F1402900), Shanghai Basic Research Program (23JC1401000), and the Major Key Project of PCL under Grant PCL2024A06.
References
[1] Darinka Dentcheva, Spiridon Penev, and Andrzej Ruszezyíski. Statistical estimation of com- posite risk functionals and risk optimization problems. Annals of the Institute of Statistical Mathematics, 69:737-760, 2017.
[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:419 449, 2017.
[3] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[4] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In International conference on machine learning, pages 1126-118 1135. PMLR, 2017.
[5] Mengdi Wang, Ji Liu, and Ethan X Fang. Accelerating stochastic composition optimization. Journal of Machine Learning Research, 18(105):1 1-3,,, 2017.
[6] Saeed Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A single timescale stochastic approximation method for nested stochastie optimization. SIAM Journal on Optimization, 30 (1):960-979, 2020.
10

---

[7] Wenqing Hu, Chris Junchi Li, Xiangru Lian, Ji Liu, and Huizhuo Yuan. Efficient smooth non-convex stochastic compositional optimization via stochastic recursive gradient descent. Advances in Neural Information Processing Systems, 32, 2019.
[8] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69: 4937-4948, 2021.
[9] Andrzej Ruszezynski. A stochastic subgradient method for nonsmooth nonconvex multilevel composition optimization. SIAM Journal on Control and Optimization, (993):2301-22222 2021.
[10] Yin Liu and Sam Davanloo Tajbakhsh. Stochastic composition optimization of functions without lipschitz continuous gradient. Journal of Optimization Theory and Applications, 198 (1):239-289) 289, 2023.
[11] Quanqi Hu, Dixian Zhu, and Tianbao Yang. Non-smooth weakly-convex finite-sum coupled compositional optimization. Advances in Neural Information Processing Systems, 36, 2024.
[12] Frank H. Clarke. Optimization and nonsmooth analysis. SIAM, 1990.
[13] Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Ali Jadbabaie, and Suvrit Sra. Complexity of finding stationary points of nonsmooth nonconvex functions. In Proc. ICML, pages 11173-
11 11182, 2020.
[14] Guy Kornowski and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Journal of Machine Learning Research, 23(314):1 2022.
[15] AA Goldstein. Optimization of lipschitz continuous functions. Mathematical Programming, 13: 14-22, 1977.
[16] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. International conference on machine learning. pages 2613-2621. PMLR, 2017.
[17] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in neural information processing systems, 31, 2018.
[18) Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. Advances Neural Information Processing Systems, 32, 2019.
[19] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. International conference on machine learning, pages 6286-6295. PMLR, 2021.
[20] Tianyi Lin, Chengyou Fan, Mengdi Wang, and Michael Jordan. Improved sample complexity for stochastic compositional variance reduced gradient. 2020 American Control Conference (ACC), pages 126-131. IEEE, 2020.
[21] Yibo Xu and Yangyang Xu. Katyusha acceleration for convex finite-sum compositional opti- mization. INFORMS Journal on Optimization, 3(4):418 -43,, 2021.
[22] Huizhuo Yuan, Xiangru Lian, and Ji Liu. Stochastic recursive variance reduction for efficient smooth non-convex compositional optimization. arXiv preprint arXiv: 13515, 2019.
[23] Maria-Luiza Vladarean, Nikita Doikov, Martin Jaggi, and Nicolas Flammarion. Linearization algorithms for fully composite optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 3669-3695. PMLR, 2023.
[24] Dionysios S Kalogerias and Warren B Powell. Zeroth-order stochastic compositional algorithms for risk-aware learning. SIAM Journal on Optimization, 32(2):386-416, 2022.
[25] Marko M Makela and Pekka Neittaanmaki. Nonsmooth optimization: analysis and algorithms with applications to optimal control. World Scientific, 1992.
11

---

[26] Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye. A gradient sampling method with complexity guarantees for lipschitz functions high and low dimensions. Advances in neural information processing systems, 35:6692-6703, 2022.
[27] Lai Tian, Kaiwen Zhou, and Anthony Man-Cho So. On the finite-time complexity and practical computation approximate stationarity concepts of lipschitz functions. International Conference Machine Learning, pages 21360-21111 21379. PMLR, 2022.
[28] Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non- convex optimization through online-to-non-comwee conversion. In International Conference on Machine Learning, pages 6643-6670. PMLR, 2023.
[29] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):277 2017.
[30] Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances Neural Information Processing Systems, 35:26160-261155 2022.
[31] Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. International Conference on Machine Learning, pages 5219-5233. PMLR, 2023.
[32] Chengchang Liu, Chaowen Guan, Jianhao He, and John Lui. Quantum algorithms for non- smooth non-convex optimization. arXiv preprint arXiv:2410. 16189, 2024.
[33] Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-depentie for zero-order nonsmooth nonconvex stochastic optimization. arXiv preprint 23Xi:23377.05544 2023.
[34] Zhuanghua Liu, Cheng Chen, Luo Luo, and Bryan Kian Hsiang Low. Zeroth-order methods constrained nonconvex nonsmooth stochastic optimization. Forty-first International Conference Machine Learning. 2024.
[35] Benjamin Grimmer and Zhichao Jia. Goldstein stationarity in lipschitz constrained optimization. arXiv preprint arXiv:23 page 9, 2023.
[36] John C Duchi, Peter L Bartlett, and Martin Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[37] John Duchi, Michael 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, (5):27888-2280 2015.
[38] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[39] Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52): 2017.
[40] Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics, pages 462-466, 1952.
[41] Tong Zhang. Analysis of multi-stage convex relaxation for sparse regularization. Journal of Machine Learning Research, 11()), 2010.
[42] Chao Qu, Yan Li, and Huan Xu. Non-convex conditional gradient sliding. In international conference on machine learning, pages 4208-4217. PMLR, 2018.
[43] Zebang Shen, Cong Fang, Peilin Zhao, Junzhou Huang, and Hui Qian. Complexities in projection-free stochastic non-convex minimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2868-2876. PMLR, 2019.
12

---

The appendix is organized as follows. Section A introduces supporting lemmas that are essential for the analysis of the proposed gradient-free SCO methods. Dection/Bjroove the convergence rate of the GFCOM method introduced in Section 4 method which enjoys better function oracle call complexity. Section provides the convergence analysis of the WS-GFCOM² and WS-GFCOM* proposed in Section
Section proves the convergence rate of the GFCOM
A Supporting Lemmas
Throughout the work, we define the variable gx(x) 5y rithm, and we denote
1, EiEbb, G(x; St.e) for the GFCOM algo-
Ebb G(x; St,s), m =
(x) =
by Σ
G(x: Ct,s), Otherwise
for the GFCOM* method. Now introduce an important lemma which is useful for the analysis of both GFCOM and GFCOM* algorithms.
Lemma A.1. Under Assumption 3.7
and 3.3
for both Algorithmss 7 and 2 it holds that
[I o g)x(x(+1) - (f (x:)
on 2
G
vd
5 "E [ 9)x()))
12 11]+ + - [|v, Vif ((f=)))(x))11
2
28
Proof. From the smoothness of 43 (f g)5. we have
(f (fog))(X(41) ())
x + cG GGVV
X1+1 -xil" x2
28
cn2 Gr2 Vd
/V(( gx) vi))
l|ve
28
on GGgV
= " (((())s(x))11-
l|vel| + 2 l|v - V(f g)x(x;)1?
"
28
Taking expectations on both sides of the inequality, we get the desired result.
B Convergence Analysis of Algorithm
Before giving the analysis of the convergence rate of Algorithm mean-square error term E [[llv, (xx)(
we first present the bound of the
Lemma B.1. Under Assumption
3.7 and
3.3
for Algorithm 7 itt holds that
2d G2o
32v 2
(x)((x))1? ||?] E [|v.
8bb
bj
Proof.
(F(ye,))e.)) F(zz.: Er,))), we have Recall that v. = by Ejepbi 28
E Iive (
<2E
1
Σ
d (F(g(x; + owe,): - F(g(xi Swir):E
by jElby]
28
d (F(g(x; -owL)): - F(g(x+ .wr.)): v(f g)s(zz)
+ 2E
Σ
by
28
jE(by]
13

---

de
Σ jE(by]
E
[IF(a(xx +wwL)): F( dwas): E(r))l
2
d²
+ bj
Σ
E
- -dw,):: Fx oww.)::
jElby]
32v 32v GT
by
2d Gzo8 32 22/2ddG2 +
82bg
by
The first inequality is due to a bl 2 < 2 +| |||||| for any a. b E Rd. The second inequality is due to Lemma 3.8 The last inequality follows from the Gy-Lipchitzness of f(-) and Assumption 3.3
We present the formal proof of Theorem 4.1 and Corollary
4.2 below.
B.1 Proof of Theorem 4.1
Proof. If we take GG and rearrange the formula in Lemma A.1 we have
! EIIV o 9)s(x))) B[(f g)6(xx) (f ()8((x(1))) + " Ellv, V o 9)((x;)1
2
Sum the above inequality from t T and divide both sides by nff have
T-1
2cG Go, V [(f (g) (x0) (f g)s(xr)
T Σ B ()(())))(x))11
8T
32 G2 26.3
bf
8bb
In addition, by Lemma 3.7 we have
[[ g)x - (fog))(())) s B[( o (xo) - (f))) +GG
Combining the last two incqualities, we get the desired result.
B.2 Proof of Corollary 4.2
Proof. The total zeroth-order oracle calls be bounded by
O(Tbrby)
GjG,VdR
GGGOVa
dGGG2
&Goo 822
=0
de2
2
G
G.GGGoo0 826
=0
9
836
C Convergence Analysis of Algorithm
In this section, we consider the formal proof of the convergence rate of the GFCOM* method. First, we introduce the following lemma bound the mean-square error between the recursive gradient estimator and the gradient of the surrogate function.
14

---

Lemma C.I. Letn = [t/mmm/ m. Under Assumption 3.1 and 3.3
for Algorithm 2 it holds that
E |Iv
Vf o g))((x,))
10md 67
32 S
Σ
+
826,
8///b//
by
==
G3
G708
8bg
628//
Proof.
By a + bl1² < 2|al| + 2 ||b|| can infer that
E Vv (f (x,))
<2E ||v. v(f o (f))(xx)))) + 2E ( (((o)))-(())))() ())((x))
To bound the first term of R.H.S., have
Billv
V( ( (xx))))
d
d (F(y-115i 1c:)),))
=E
25
28
5E(
+V--1 v(f o (x)
d
d ( - (c,
=E
Σ
;
26
28
5E[D/]
(V(f (x))
v( o( + + V(fo---
d (F(y.ji F
d (F(y -
28
17
26
28
JEIY
+ E
||v-11 11-11 v(
The second equality follows from Lemma ||[[x|]
3.8 The last inequality is due to [E[[ [8x]]1 s
Observe that
d (F(y F F(z- ((.)))
(F(y F((.s)))))(
25
28
<5E
(F(g(xi + oww.)) - F(g(x: Er.s):
28
(F(g(xi-1 + + -(1(- - -.. wa.
+ 5E
[F(((x + tw..)) - Flyo,i (..))
28
+ 5E
(F(g(x: Sw.)):Er.)) - F Wis
28
+ 5E
[((((x-1 + ow.,): F )
Wt.j
25
27
+ 5E
(F(g(xi-1 -Sw1,): F F(zz-1.5 E(.))
26
15

---

G
+ 5d G7
E
||x,
-x 11
8²
826
G 82
5d G7od
E
||ve_111]
+
826
The first incquality is due to || +... | S 1l..
+....7 n ||, 1! The second inequality is
due to the Lipschitzness of both inner and outer functions with Assumption 3.3 Consequently, one has
E
V(f o (x))(x)))1
5d
5d
G308
E
||v
+E [[v1-11 VV (((0)))))((xx-)I
8201,
826
5md G308
16v2ndG
[v:11
8
by
The last inequality follows from Lemma 3.8 In addition, for t mod 0 we can bound
E
|V (f 9()((x)) v(f off ((fo))((x))1
d
E
Eu
((f + ōu) g)x, + ou))
[
[I(f o + +ōu) ()x أu)l1 ||]||]
Eu
8
82by
The last inequality follows from the Lipschitzeess of f and Assumption 3.3 we can bound
Similarly, for t mod m of
Gd2
E (())))( (( g)sx))) S
888
Putting everything together, we get the desired bound.
present the formal proof of Theorem 4.3 and Corollary
below.
C.1 Proof of Theorem Proof. Rearrange the terms in Lemma A.I sum t from 0 to T 1, and divide both sides by xT 2
Σ [V( o o))(1))
2E [V o g)x(xo) - 2( o g)s(xT)]
(1 GgG T
B 12
8
1 E V(S V(J
2E (f 9)8(x0) - 2(1 g)x(XT)]
( onG Va
10md 10md&G? G?G
E [|v:11]]
nI
T
52b/,
10mo&Go0z 826/,b//
32V2ndG2, G2
2nd Ged
Gof
by
8zby
826 9
16

---

The last inequality follows from Lemma
C.I If we choose hyperparameters as follows
5
dG (GG(GO)) (
m = (G
b/ =
θ
=
GoG Vd
E
Then we can deduce that 1 onG 13
1 0. By Lemma 3.7 we have
E [(f o (xo) - (J g) & ()([og)((x)) - (ʃ +
Therefore, we obtain the following result
E [[V0)(xx)) =0 (vāC, ( VaG.G.
doio,
&C
8T T
bj
8b
8%6/
C.2 Proof of Corollary 4.4
Proof. The total zeroth-order oracle calls can be bounded by
O + Tbybg/m)
ViG
vaGaog
dG,G,
dCgot
8e2
2
862
de..GGGBBB
83
82e
D Extensions Convex Nonsmooth Functions
In this section, we present the formal proof of theorems presented in Section 5
D.1 Proof of Theorem 5.2
Proof. Since G(=: () is convex function, gc(-) is also convex. Using the result of Section 3.2.4 of [8
and Assumption 5.1 we can deduce that f o is convex function. Let x arg (f gx)(x).
then we have
[l(f o gr)s(x)) (f gx)((")]]
(V 9c)6 (x1), xx)]
d
(F(g((x + (du) - F(g.(x: -8)) E:), - x
28
1
E
(x,
X,+1, xx)]
770
||xx
x11 ||x x=1 + ||x; - 1xxx++11 12
2/j0
||xx
x11 ||x++1 x x*1]] 8 2.ddGGGGGGm
21J0
The first inequality follows from the convexity of f gt- The last inequality is due to Lemma 3.8 Observe that for Vx E Rdd
((fog)s(x)- g()(())
=|E,,[[ ( (x ōu)] Enl(s gx) Su)]
=[Eul[fo o [) ōu) (f) + ou]]]
<Eullf gx őu) gx) du)]]
17

---

0o
6..0
where C1 is some constant. The second equality is due to the linearity expectations. The last
inequality follows from Assumption 3.3 and Lipschitzness of f. Consequently, have
E[( (x)( - [x)))(xx*
R + G + 201 200
To
vb2,0
G2RG
2/
VTo
Vbg.0
By Lemma 3.7
we have
[(f o g)s(x1) (f (fog)((x))) s El(s o (f (fo (2
GG,
Consequently, one has
E[(s o ()x(x)) (fog))((x))
G2 2c1 G00 2G
VTo
vb,0
To obtain [B[(S o (x)( (ʃ ( gx()x)] P. we choose
R
GGod
(G/G.)
100 GyG,VaTo
To -
0g,0 =
8 8=6 Q
0²
p²
D.2 Proof of Corollary 5.3
Proof. The total stochastic function oracle calls can bounded by
o (Tbyby + Tobg,o)
GjG,va(p GGGg8)
dGg.22
&Gjoo
afe.40308
662
822
p²
G
GRGGGG00
836
826
p
d3 @RAAGGAGG G 0
821,18
826
D.3 Proof of Corollary 5.4
Proof. The total stochastic function oracle calls can be bounded by
o (Tb, + Tbyby/m + Tobg.0)
G GJG.vdlo GG dG,G, PogGz
diPC4 Go
de2
82
p
die NS 8
=0
83
pr
d 82
=0
824
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are 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 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an 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]
19

---

Justification:
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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 be properly referenced.
4. Experimental Result Reproducibility
Question: 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 whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
20

---

Answer: [No]
We are clearing the code with internal compliance and will release it upon approval.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
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 SonddeSubmissioPPP.
//nips.cc/pp wwwppbblccgguiicuceccccceoe.oopp
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: [Yes]
Justification:
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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
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).
21

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is 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 of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not 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 the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://aaarag..ccppaaa/a//aaaaaa
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have 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: There are potential positive negative societal impacts of this work.
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 socictal impact 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.
22

---

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 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 MI..
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:
Guidelines:
The answer NA means that the paper poses 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. Lieenses 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: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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 of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not 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:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl 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 an 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 screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not 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 the NeurIPS Code of Ethies, workers involved in data collection, curation, or 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 does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 we 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 as the institution conducting the review.
24


Reviews:
[{"review_id": "fNFJaTbb0y", "reviewer": "Reviewer_iZH7", "summary": "This paper studied the zero-order method for computing an approximately stationary point for a Lipschitz function with a composition structure. The main difficulty lies in the function value evaluation. The composition structure involves multiple expectations, requiring multiple rounds of sampling to obtain a satisfactory estimation. The authors also discuss the situation when the objective function is convex. They show that the complexity can be improved under the convexity assumption.", "questions": "See above.", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I think this is an okay paper, in the sense that it makes a meaningful contribution to an important setting that was previously unexplored. The technique is intuitive, and the proof is very neat and clean, which is good and should be easy to follow.", "weaknesses": "My impression is that the technique is okay but not that surprising. There are two expectations, so two sampling sequences are needed to evaluate the function value. I would say the technical contribution is a little bit insufficient, but I do not strongly oppose it solely on this point.\n\nThe following are minor points: \n* I would recommend specifying the distribution P in the main text, rather than in the statement of Lemma 3.7. It seems the definition of f_\\delta appears in L134, with a very general distribution P following. The definition of this P is not specified even in Algorithms 1 and 2. \n* L118: \\mathbb{B}(x, \\delta) should be \\mathbb{B}_\\delta(x), according to L93. \n* Theorem 4.1, Corollary 4.2, Theorem 4.3, etc.: The upper bound on gradient norm should be in the sense of expectation, right? It seems highly non-trivial to exactly select one R \\in [T] such that the gradient norm is minimal in the telescoping sum, due to the difficulty in evaluating the gradient of the smoothed function. \n* For Section 5, I recommend considering studying tighter stationarity notions for convex functions, e.g., those whose definition requires weak convexity. The notion of a Goldstein approximate stationary point is rather loose. Thus, whenever possible, considering tighter solution notions would be better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer iZH7 for your careful review and insightful suggestions.\n\n**Q1:**  I would recommend specifying the distribution $P$ in the main text, rather than in the statement of Lemma 3.7. It seems the definition of $f_\\delta$ appears in L134, with a very general distribution P following. The definition of this P is not specified even in Algorithms 1 and 2.\n\n**A1:** Thanks for your suggestion. We will explicitly state that $P$ presents the uniform distribution in the unit ball in the revision.\n\n**Q2:** L118: $\\mathbb{B}(x, \\delta)$ should be $\\mathbb{B}_\\delta(x)$, according to L93.\n\n**A2:** Thanks for your careful review. We will unify the notations in the revision.\n\n**Q3:** Theorem 4.1, Corollary 4.2, Theorem 4.3, etc.: The upper bound on gradient norm should be in the sense of expectation, right?\n\n**A3:** Thanks for your careful review. It should be the gradient norm in expectation, and we will fix it in the revision.\n\n**Q4:** For Section 5, I recommend considering studying tighter stationarity notions for convex functions, e.g., those whose definition requires weak convexity. The notion of a Goldstein approximate stationary point is rather loose. Thus, whenever possible, considering tighter solution notions would be better.\n\n**A4:** We agree that $(\\delta, \\epsilon)$-goldstein stationary point is not a tight notion for convex functions. \nFor the convex problem, we can study other notions such as the optimal function value gap and the nearly approximate stationary point (Davis et al. [a]).\n-  For the optimal function value gap,  Lemma 5.2 has shown that we can achieve $\\mathbb{E}[\\Phi(x_T)- \\Phi^*]\\leq \\rho$ with $\\mathcal{O}(d \\hat{R}^2 G_f^4 G_g^2 \\sigma_0^2\\rho^{-4})$ function value query calls.\n- For the nearly approximately stationary point, Davis et al. [a] have shown that the explicit convergence rates can be achieved by minimizing the weakly-convex (possibly nonsmooth) function.  We think the convergence analysis based on this notion can also be achieved in the compositional optimization problem by introducing the proximal point iterations in the algorithm design.\n\n**Reference**\n- [a] Damek Davis, and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal on Optimization 29.3 (2019): 1908-1930.", "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": "skSxOHQrbH", "reviewer": "Reviewer_ZyfL", "summary": "This work proposes two zeroth-order methods (including one variance-reduced method) for solving non-convex non-smooth stochastic compositional optimization (SCO). These two methods are further extended to solving convex non-smooth SCO. Theoretical analysis are provided to show the convergence guarantee of all proposed methods.", "questions": "Please see the weakness section.", "limitations": "No significant limitations in this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main contribution of this work is that it proposes the first zeroth-order methods for non-smooth SCO under non-convex and convex setting and presents convergence analysis. The paper is well-written and easy to follow.", "weaknesses": "My main concern is in the novelty of the proposed methods and their convergence analysis. Base on my understanding, the proposed four methods are extensions of the existing work [31]. [31] proposed four zeroth-order methods (GFM, GFM+, WS-GFM, WS-GFM+) for solving non-smooth optimization without compositional structure under both non-convex and convex setting. Based on GFM in [31], the GFCOM in this work simply replaces the stochastic function values in the gradient estimators into stochastic function values of the compositional function, and use large batches to ensure the accuracy of the inner function value estimation. The convergence analysis is thus similar to GFM as well. \n\n\nReference.\n\n[31] Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. In International Conference on Machine Learning, pages 5219–5233. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer ZyfL for your insightful review.\n\n**Q1:**  My main concern is in the novelty of the proposed methods and their convergence analysis. Base on my understanding, the proposed four methods are extensions of the existing work [31].\n\n**A1:**  This is the first work that proposes stochastic algorithms to solve the general nonconvex nonsmooth stochastic compositional problem with non-asymptotic convergence rates. Note that both the algorithm design and the convergence analysis of previous work for nonconvex nonsmooth stochastic compositional optimization problems require additional assumptions such as weak convexity [11] and relative smoothness [10].\n\nOur algorithm design and convergence analysis are not simple extensions of existing work [31]. In this work, we apply the randomized smoothing on $\\Phi(\\mathbf{x})$ to construct its smoothing surrogate $\\Phi_{\\delta}(\\mathbf{x})$. \nHowever, achieving a sufficient accurate function value of a surrogate compositional problem $\\Phi_{\\delta}(\\cdot)$ to guarantee convergence is more difficult than the counterpart in the problem without compositional structure. Additionally, obtaining a smoothing surrogate $\\Phi_{\\delta}(\\mathbf{x})$ does not result in any smoothing surrogate of $f$ or $g$.\nTherefore, we have to carefully use the Lipschitz continuity of $f$ and $g$ (rather than the smoothness of their surrogate functions) to bound the expected gradient estimation error (see Lemma B.1 and C.1) with reasonable sample complexity,  which is more complicated than previous work for non-compositional problems that can directly use the smoothness of the surrogate function of objective [31].\n\n**Reference**\n- [10] Yin Liu, and Sam Davanloo Tajbakhsh. Stochastic Composition Optimization of Functions Without Lipschitz Continuous Gradient. Journal of Optimization Theory and Applications 198.1 (2023): 239-289.\n- [11] Quanqi Hu, Dixian Zhu, and Tianbao Yang. Non-smooth weakly-convex finite-sum coupled compositional optimization. Advances in Neural Information Processing Systems 36 (2024).\n- [31] Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. International Conference on Machine Learning. PMLR, 2023.", "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": "cV8jpbYKiF", "reviewer": "Reviewer_nNfG", "summary": "This paper investigates stochastic compositional optimization (SCO) problems, which are popular in many real-world applications. The authors focus on nonconvex and nonsmooth SCO, and propose gradient-free stochastic methods for finding the $(\\delta,\\epsilon)$-Goldstein stationary points of such problems with non-asymptotic convergence rates. Furthermore, they also use variance reduction technique to accelerate their algorithms with improved results.", "questions": "* My primary concern is whether $\\mathbf{v}\\_t$ in Algorithm 1 is an unbiased estimator of $\\nabla \\Phi\\_\\delta (\\mathbf{x}\\_t)$. Although Lin et al. (2022) have proven that $\\mathbf{v}\\_t$  in Eq. (2) is an unbiased estimator of $\\nabla f\\_\\delta (\\mathbf{x})$, such gradient estimation cannot be directly applied to the SCO problem by introducing auxiliary variables $\\mathbf{y}\\_t$ and $\\mathbf{z}\\_t$ in Eq. (3). Specifically, although the estimation of each layer function and its gradients is unbiased, i.e., $\\mathbb{E}\\_{\\xi\\_1} [F(\\mathbf{x};\\xi\\_1)]=f(\\mathbf{x})$, $\\mathbb{E}\\_{\\xi\\_1} [\\nabla F(\\mathbf{x};\\xi\\_1)]=\\nabla f(\\mathbf{x})$, and $\\mathbb{E}\\_{\\xi\\_2} [G(\\mathbf{x};\\xi\\_2)]=g(\\mathbf{x})$, the main challenge in SCO lies in obtaining an unbiased estimation of gradient $\\nabla f(g(\\mathbf{x}))$. This is because the expectation over $\\xi\\_2$ cannot be moved inside of $\\nabla f$ such that $\\mathbb{E}_{\\xi_1,\\xi_2} [\\nabla F(G(\\mathbf{x};\\xi_2);\\xi_1)]\\neq \\nabla f(g(\\mathbf{x}))$. \n* The proposed algorithms in this paper appear to be a direct application of existing algorithms [1] to the SCO problem. Additionally, the accelerated algorithms employ variance reduction technique, which have already been widely used for other  settings in SCO problems [2,3]. Could you elaborate more details on the technical challenge and novelty of your work? \n\n[1] Lin et al. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. NeurIPS, 2022. \n\n[2] Yuan et al. Efficient smooth non-convex stochastic compositional optimization via stochastic recursive gradient descent. NeurIPS, 2019. \n\n[3] Zhang and Xiao. A stochastic composite gradient method with incremental variance reduction. NeurIPS, 2019.", "limitations": "See above", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "* The study of the SCO problem is highly significant, and the research on gradient-free algorithms is also of considerable value. \n* This paper is well-written and easy to understand.", "weaknesses": "* The technical novelty of this work is limited, as the proposed algorithms are mostly based on SGFM [1]. \n* The authors do not prove that $\\mathbf{v}\\_t$ is an unbiased gradient estimator of $\\nabla \\Phi_\\delta (\\mathbf{x}_t)$ (See Question 1 for details). \n* The authors utilize variance reduction technique to accelerate their algorithms. However, they do not review some important related work on variance reduction in this paper, e.g., SVRG, STORM and so on. \n\n[1] Lin et al. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. NeurIPS, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer nNfG for your detailed review.\n\n**Q1:** The authors utilize variance reduction technique to accelerate their algorithms. However, they do not review some important related work on variance reduction in this paper, e.g., SVRG, STORM and so on.\n\n**A1:** Thanks for the suggestion. We will provide a more detailed literature review of variance reduction techniques in the revision, including SVRG [10] and STORM [9].\n\n**Q2:** The authors do not prove that $\\\\mathbf{v_t}$ is an unbiased gradient estimator of $\\nabla \\Phi_{\\delta}(\\mathbf{x}_t)$\n\n**A2:**  We emphasize that our algorithm design and theoretical analysis do not require ${\\mathbf v}_t$ to be unbiased. \nIn contrast, we focus on providing the upper bound on the expected gradient estimation error, e.g. Lemma B.1 (line 410-415).\nThe sharp gradient estimation error indeed leads to reasonable convergence rates (e.g., Theorem 4.1) even if the estimator is biased.\n\nFurthermore, solving the nonconvex stochastic (compositional) optimization problem with a biased gradient estimator is very popular in literature Ref. [2,3,4,5,8,9].\nFor example, Zhang and Lin [3] applied the biased gradient estimator to solve a smooth stochastic compositional optimization problem, and their introduction mentioned \n**Using biased gradient estimators can cause various difficulties for constructing and analyzing randomized algorithms, but is often inevitable in dealing with more complex objective functions other than the empirical risk.**\n\n**Q3:**  The proposed algorithms in this paper appear to be a direct application of existing algorithms [1] to the SCO problem. Additionally, the accelerated algorithms employ variance reduction technique, which have already been widely used for other settings in SCO problems [2, 3]. Could you elaborate more details on the technical challenge and novelty of your work?\n\n**A3:** The theoretical results in our work cannot be obtained by combining the techniques of Ref. [1,2,3].\nNotice that the convergence analysis of the existing work [2, 3] heavily depends on the smoothness of both the outer function $f$ (or its differentiable term) and the inner function $g$. \nIn this work, both $f$ and $g$ may be nonsmooth,  leading to the nonsmooth compositional function $\\Phi(\\mathbf{x}) = (f \\circ g)(\\mathbf{x})$.\nWe only apply the randomized smoothing technique [1] on $\\Phi(\\mathbf{x})$ to construct its smoothing surrogate $\\Phi_{\\delta}(\\mathbf{x}) = (f \\circ g)_{\\delta}(\\mathbf{x})$.\nHowever, it does NOT lead to any smoothing surrogate of $f$ or $g$, which means we cannot directly combine the analysis of Ref. [1, 2, 3].\nIn contrast, we need to use the Lipschitz continuity of $f$ and $g$\n(rather than their smoothness) to carefully bound the expected mean squared error with reasonable sample complexity (see Lemma B.1 and C.1), which is quite different from the analysis in smooth case [1, 2, 3].\n\n**Reference**\n- [1] Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems 35 (2022): 26160-26175.\n- [2] Huizhuo Yuan, Xiangru Lian, and Ji Liu. Stochastic recursive variance reduction for efficient smooth non-convex compositional optimization. arXiv preprint arXiv:1912.13515 (2019).\n- [3] Junyu Zhang, and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. Advances in Neural Information Processing Systems 32 (2019).\n- [4] Mengdi Wang, Ethan X. Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming 161 (2017): 419-449.\n- [5] Mengdi Wang, Ji Liu, and Ethan X. Fang. Accelerating stochastic composition optimization. Journal of Machine Learning Research 18.105 (2017): 1-23.\n - [6] Yin Liu, and Sam Davanloo Tajbakhsh. Stochastic Composition Optimization of Functions Without Lipschitz Continuous Gradient. Journal of Optimization Theory and Applications 198.1 (2023): 239-289.\n- [7] Quanqi Hu, Dixian Zhu, and Tianbao Yang. Non-smooth weakly-convex finite-sum coupled compositional optimization. Advances in Neural Information Processing Systems 36 (2024).\n - [8] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances in neural information processing systems 31 (2018).\n - [9] Ashok Cutkosky, and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. Advances in neural information processing systems 32 (2019).\n - [10] Rie Johnson, and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems 26 (2013).", "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": "kFuw9cEtL5", "reviewer": "Reviewer_VEqR", "summary": "The authors propose a zero-th order algorithm for Stochastic Compositional Optimization (SCO) problems. Such problems are given in the form of a composition of two functions, each of them being random depending, and the corresponding objective should be minimizer in expectation. The authors consider the nonsmooth nonconvex setting and propose an algorithm which to tackle such problems. The algorithm is called GFCOM, and a variance reduction variant, GFCOM+ is proposed. The authors propose a complexity analysis for the proposed method, with explicit estimates for reaching Goldstein approximate stationary points. They extend their analysis to the convex setting and conclude with numerical experiments and a comparison with the method of Kiefer-Wolfowitz.\n\nI did not read all the details of the proof of the variance reduced algorithm and the convex analysis.", "questions": "Lemma 3.7 and 3.8, what are the precise references to the paper of Lin et al, which part of the paper do the authors refer to?\n\nAre the random variables $\\xi$ and $\\zeta$ independent? If yes it should probably be stated.\n\nThis sentence is misleading: \"hard instances have shown that finding an $\\epsilon$-stationary point with respect to the Clarke subdifferential of a Lipschitz function in finite time is computationally intractable\". Being $\\epsilon$ stationary is not the right notion for nonsmooth optimization: even in the convex setting, the subdifferential does not tend to 0. The hardness result of Kornowski and Shamir is actually different from what is suggested by the sentence and relates to the impossibility of getting close to the critical set.\n\nTable 1: what is WS-GFCOM?\n\nThis sentence is misleading: \"Consequently, they considered a refined notion of approximate stationary point in terms of the Goldstein $\\delta$-subdifferential\". Kornowski and Shamir do not use this notion.\n\nSection 6: what is the underlying compositional structure? What are the random variables?\n\nEquality (2) is extremely misleading as a different expression is used in the algorithms and proofs.", "limitations": "Section 4.2, what is the value of $c$. Without this the algorithm cannot be implemented.\n\nThe convex section is probably of more limited interest than the rest.\n\nThe paper should probably contain a discussion, comparing the obtained complexity estimate with the more usual zero-th order stochastic optimization literature. What is the added cost of the stochastic compositional structure?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written, the assumptions are clearly presented. The analysis flows well and looks technically solid.", "weaknesses": "The numerical section does not seem to use a specific compositional structure, so it constitutes a weak illustration of the relevance of the method. The paper fail to provide a convincing motivating example related to machine learning.\n\nThe value of $c$ should be given to actually implement the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer VEqR for your insightful and detailed review. Here we would like to address your concern.\n\n**Q1:** What are the precise references to the paper of Lin et al.?\n\n**A1:**  Lemma 3.7 refers to Proposition 2.3 of Lin et al. [30], and Lemma 3.8 refers to Lemma D.1 of Lin et al. [30]. \nWe will include these details in the revision.\n\n**Q2:** Are the random variables $\\mathbf{\\xi}$ and $\\mathbf{\\zeta}$ independent? \n\n**A2:**  Yes, these two random variables are independent. We will explicitly state this point in the revision.\n\n**Q3:** The hardness result of Kornowski and Shamir is different from what is suggested by the sentence.\n\n**A3:** We will rephrase this sentence to avoid confusion in the revision.\nSpecifically, Zhang et al. [13] showed that no deterministic algorithms can find an $\\epsilon$-stationary point with respect to the Clarke subdifferential in finite time.\nThey construct the lower bound with a resisting oracle, so their result only holds for deterministic algorithms that generate a fixed sequence.\nLater, Kornowski and Shamir [14] showed that no randomized algorithms can find an $\\epsilon$-near approximately stationary point in finite time with a probability of almost 1.\nIt can be inferred from their result that no deterministic or randomized algorithm can find an $\\epsilon$-stationary point in finite time since the $\\epsilon$-stationary point is a tighter convergence notion than the $\\epsilon$-near approximately stationary point.\n\n**Q4:** What is WS-GFCOM?\n\n**A4:** It is the warm-started GFCOM method (lines 218-219), which is presented in Section 5 for the convergence analysis of the convex nonsmooth SCO problem.\nThe details of WS-GFCOM are presented in Algorithm 3.\n\n**Q5:** Kornowski and Shamir do not use this notion.\n\n**A5:** Thanks for your careful review. The refined notion in terms of Goldstein $\\delta$-subdifferential was proposed by Zhang et al. [13]. We will correct the citation in the revision.\n\n**Q6:** What is the underlying compositional structure? What are the random variables?\n\n**A6:** We provide the details for the compositional formulation of these problems below.\n\n1. For the portfolio management problem (6), we formulate it as\n$$\\min \\Phi(x)= \\mathbb{E}[F(\\mathbb{E}[G(x;\\zeta)];\\xi)]$$\nwhere\n $$G(x;\\zeta)= \\left[x_1, \\ldots, x_N,  \\langle r_{\\zeta}, x \\rangle\\right]^{\\top}$$\nand\n$$F(w;\\xi)=- \\langle r_{\\xi}, w_{[N]}\\rangle + (\\langle r_\\xi, w_{[N]}\\rangle - w_{N+1})^2 + \\beta (x).$$\nThe random variables in the above formulation are $\\xi$ and $\\zeta$.\nBoth of $\\xi$ and $\\zeta$ are uniformly sampled from $\\\\{1,\\ldots,T\\\\}$.\n2. For the Bellman residual minimization problem (after line 271), we formulate it as\n$$\\\\min\\\\Phi(w)=\\\\mathbb{E}[F(\\\\mathbb{E}[G(w;\\\\zeta)];\\\\xi)]$$\nwhere\n$$ G(w; \\zeta) = [\\langle \\psi_1, w \\rangle,  r_{1, \\zeta_1} + \\gamma \\langle \\psi_{\\zeta_1}, w \\rangle, \\ldots, \\langle \\psi_n, w \\rangle,  r_{n, \\zeta_n} + \\gamma \\langle \\psi_{\\zeta_n}, w \\rangle]^{\\top}$$\nand\n$$ F(z; \\xi) = h(z_{2 \\xi} - z_{2\\xi+1}).$$\nThe random variables in above formulation are $\\zeta = [\\zeta_1, \\ldots, \\zeta_n]^{\\top}$ and $\\xi$. Specifically, each $\\zeta_i$ is uniformly sampled from $\\\\{P_{i 1}, \\ldots, P_{i,n}\\\\}$ and $\\xi$ is uniformly sampled from $\\\\{1,\\dots,T\\\\}$.\n\nWe will provide the above explicitly compositional formulation in the revision.\n\n**Q7:** Equality (2) is extremely misleading as a different expression is used in the algorithms and proofs.\n\n**A7:** Thanks for your careful review. We will use different notations in Equality (2) to distinguish $v_t$ in the algorithm in the revision.\n\n**Q8:** What is the value of $c$. \n\n**A8:** According to Lemma 8 of Duchi et al. [33], we can take $c=1$ when $\\mathcal{P}$ is the uniform distribution in the unit ball.\nWe will provide this explanation in the revision.\n\n**Q9:** The convex section is probably of more limited interest than the rest.\n\n**A9:** We agree that the contribution for the nonconvex case is more interesting, while the convex case is also an important class of problems.\nIn Section 5, we show that convexity can result in the improved convergence guarantee to find the $(\\delta, \\epsilon)$-Goldstein stationary point.\n\n**Q10:** The paper should probably contain a discussion, comparing the obtained complexity estimate with the more usual zero-th order stochastic optimization literature.\n\n**A10:** Thanks for your suggestion. We present the function query complexity of zeroth-order methods for different classes of stochastic optimization problems in the following table.\n\n| Methods  | Problem | Complexity | Reference |\n| -------- | ------- | ------- | ------- |\n| GFM | $\\min f(x)$ | $\\mathcal{O}(d^{1.5}\\delta^{-1}\\epsilon^{-4})$ | [30] |\n| GFM+ | $\\min f(x)$ | $\\mathcal{O}(d^{1.5}\\delta^{-1}\\epsilon^{-3})$ | [31] |\n| Online to Nonconvex | $\\min f(x)$ | $\\mathcal{O}(d \\delta^{-1}\\epsilon^{-3})$ | [32] |\n| GFCOM | $\\min f(g(x))$ | $\\mathcal{O}(d^{3.5} \\delta^{-3}\\epsilon^{-6})$ | Corollary 4.2 |\n| GFCOM+ | $\\min f(g(x))$ | $\\mathcal{O}(d^{3.5} \\delta^{-3}\\epsilon^{-5})$ | Corollary 4.4 |\n\n**Reference**\n- [13] Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. ICML 2020.\n- [14] Guy Kornowski, and Ohad Shamir. Oracle complexity in nonsmooth nonconvex optimization. Neurips 2021.\n- [30] Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Neurips 2022.\n- [31] Lesi Chen, Jing Xu, and Luo Luo. Faster gradient-free algorithms for nonsmooth nonconvex stochastic optimization. ICML 2023.\n- [32] Guy Kornowski, and Ohad Shamir. An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization. JMLR 2024.\n- [33] John C. Duchi, Peter L. Bartlett, and Martin J. Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization 22.2 (2012): 674-701.", "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:

Meta-review: The paper considers methods (GFCOM, GFCOM+) to solve the problem of stochastic composite optimization (composition of two functions which are each stochastic) under very relaxed assumptions - notably no smoothness nor convexity assumptions. The methods proposed are zeroth-order in the sense of function iterations and are designed to find an approximate Goldstein stationary point. Analysis is given for both the convex and nonconvex cases and some numerical experiments are included as well.

It is agreed that the paper is well-written and clear in its presentation, i.e., all mathematical statements are precise and theorems are rigorously proven. It is also agreed by all reviewers that the method is interesting.

The weaknesses brought up by reviewers focus on the novelty of the work and the impact of the numerical experiments. Some reviewers called the results unsurprising. However, although the algorithm itself is not particularly innovative it seems that all reviewers agree that the analysis is novel and interesting (after the rebuttal).

Most reviewers engaged in the rebuttal discussion, although some simply opted to keep their score. One reviewer raised their score from a four to a five while another raised their score from a three to a five. It seems that the criticisms the reviewers initially had about the novelty of the work and any technical hangups were sufficiently addressed in the rebuttal stage. The technical soundness of the work has been confirmed by the reviewers’ response to the rebuttal. I did not feel the need to discuss the work with the reviewer after the rebuttal discussion because it was clear from the discussions that had already taken place that the problems were addressed and this was a work with mostly positive reviews.

I recommend to accept the paper.
Decision: Accept (poster)