Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization

Authors: zhuanghua  liu
luo  luo
bryan  kian
hsiang  low
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 10:25:00

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.

Main paper: 
 introduction: 
 In this paper, we consider the following stochastic compositional optimization (SCO) problem:EQUATIONwhere the outer and inner functions f : R m → R and g : R d → R m has the form of f (y) ≜ E ξ [F (y; ξ)] and g(x) := E ζ [G(x; ζ)],and the stochastic components F (y; ξ) and G(x; ζ) are Lipschitz continuous but possibly nonconvex and nonsmooth. Random variables ξ and ζ are independent. Such formulation is popular in many realworld applications, including risk management [1] , statistical learning [2] , reinforcement learning [3] , and model agnostic meta-learning [4] .Most of the existing work [2, 5, 6, 7, 8] for nonconvex SCO problem is based on the assumption that both functions f (•) and g(•) are smooth. Unfortunately, many modern machine learning Table 1 : We present the stochastic zeroth-order complexity of proposed algorithms for solving nonsmooth stochastic compositional optimization problems.The non-smoothness in the Problem (1) implies the classical gradient-based approaches and the convergence measure in terms of the gradient norm cannot be applied. The Clarke subdifferential [12] 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 ϵstationary point with respect to the Clarke subdifferential of a Lipschitz function in finite time [13, 14] .To address this issue, Zhang et al. [13] proposed a refined notion of the (δ, ϵ)-Goldstein stationary point in terms of the Goldstein δ-subdifferential, which considers the convex hull of the Clarke subdifferential at points in the δ-neighbourhood [15] .In this paper, we propose a zeroth-order stochastic method called gradient-free compositional optimization method (GFCOM) for solving Problem (1) in finite time. In particular, we show that the GFCOM can find a (δ, ϵ)-Goldstein stationary point of the objective function Φ(•) = f (g(•)) within the stochastic zeroth-order oracle complexity of O(d 3.5 δ -3 ϵ -6 ). Furthermore, we improve the GFCOM by using the variance reduction technique [16, 17, 18, 19] to establish a more efficient first-order oracle estimator, leading to the algorithm GFCOM + which achieves a tighter upper complexity bound of O(d 3.5 δ -3 ϵ -5 ). In addition, we study convex nonsmooth SCO problems. In this regime, prior methods [2, 20, 21] suffer two major limitations: (i) Their convergence analysis is based on the smoothness condition of the outer function. (ii) Their convergence result is measured 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 a (δ, ϵ)-Goldstein stationary point within O(d 3 δ -2.4 ϵ -4 + d 3.5 δ -2 ϵ -5 ) stochastic zeroth-order oracle complexity. We summarize the complexity of proposed methods in Table 1 .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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 In this section, we review prior work for stochastic compositional optimization and classical nonconvex nonsmooth 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 extrapolation-smoothing scheme, and Ghadimi et al. [6] proposed a single time-scale approach to accelerate the convergence further. Additionally, Hu et al. [7] , Lin et al. [20] , 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.Compared with the smooth counterpart, the study of nonsmooth compositional optimization is relatively scarce. Ruszczynski [9] proposed a 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 [10] introduced the stochastic composition Bregman gradient method and provided a non-asymptotic convergence analysis under the relative smoothness condition. Vladarean et al. [23] proposed a Frank-Wolfe algorithm for constrained nonconvex nonsmooth SCO problems. Their analysis assumes that the outer function is convex but possibly non-differentiable, and the inner function is smooth. Very recently, Hu et al. [11] 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-decreasing. In addition, Kalogerias and Powell [24] studied the zeroth-order stochastic optimization for a specific compositional optimization problem in risk-aware learning.In this subsection, we present a 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. [13] provided the nonasymptotic complexity analysis of the interpolated normalized gradient descent method to achieve a (δ, ϵ)-Goldstein stationary point of a Lipschitz function with a nonstandard subgradient oracle. Davis et al. [26] , Tian et al. [27] improved this method by introducing random perturbations in each iteration to remove the assumptions. Recently, Cutkosky et 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 gradientfree methods for this problem by establishing a relationship between the Goldstein δ-subdifferential and randomized smoothing. Chen et al. [31] , Liu et al. [32] improved their results by leveraging the variance-reduction technique. Kornowski and Shamir [33] obtained a 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 (1).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 are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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.We use ∥•∥ to denote the Euclidean norm of a vector. We define B δ (x) ≜ {y ∈ R d : ∥y -x∥ ≤ δ} as the Euclidean ball centered at x ∈ R d with a radius δ > 0. We let conv(A) be the convex hull of the set A. For two given sets A and B, we define A × B as their Cartesian product. In addition, we denote f • g as the function composition such that(f • g)(x) ≜ f (g(x)).Throughout this paper, we assume the objective function (1) satisfies the following assumptions. Assumption 3.1. We assume the stochastic componentF (•, ξ) is L f (ξ)-Lipschitz for any given ξ, and the stochastic component G(•, ζ) is L g (ζ)-Lipschitz for any given ζ. That is, it holds |F (x, ξ) -F (y, ξ)| ≤ L f (ξ) ∥x -y∥ and ∥G(x, ζ) -G(ŷ, ζ)∥ ≤ L g (ζ) ∥x -ŷ∥ ,for any x, y ∈ R d and x, ŷ ∈ R m . We also assume the Lipschitz parameters L f (ξ) and L g (ζ) have bounded second-order moments such thatE ξ [L f (ξ) 2 ] ≤ G 2 f and E ζ [L g (ζ) 2 ] ≤ G 2 g for some constants G f , G g > 0.Remark 3.2. We can verify that Assumption 3.1 implies the function f (•) is G f -Lipschitz, and the function g(•) is G g -Lipschitz by Jensen's inequality. Assumption 3.3. We assume that there exists a constant σ 0 as the upper bound on the variance of the functions G(•, ζ), such that for any x ∈ R d , we haveE ζ ∥G(x, ζ) -g(x)∥ 2 ≤ σ 2 0 .Assumption 3.4. We assume that the composite functionΦ(•) ≜ (f • g)(•) is lower bounded such that Φ * ≜ inf x∈R d Φ(x) > -∞.We introduce the definitions of the Clarke subdifferential and approximate Clarke stationary points.Definition 3.5 (Clarke [12] ). The Clarke subdifferential of a Lipschitz function f at a point x is defined as ∂f (x) ≜ conv {g : g = lim x k →x ∇f (x k )}. Furthermore, we call a point x an ϵ-Clarke stationary point of f if it holds that min{∥g∥ : g ∈ ∂f (x)} ≤ ϵ.Zhang et al. [13] , Kornowski and Shamir [14] showed that no deterministic or randomized algorithm could find an ϵ-Clarke stationary point in finite time. Consequently, Zhang et al. [13] considered a refined notion of approximate stationary point in terms of the Goldstein δ-subdifferential.Definition 3.6 (Zhang et al. [13] ). Given a Lipschitz function f : R d → R and δ > 0, the Goldstein δ-subdifferential of f at point x ∈ R d is defined as ∂ δ f (x) := conv(∪ y∈B δ (x) ∂f (y)), which is the convex hull of the Clarke subdifferential at the points in the δ-neighbourhood of x. Additionally,a point x ∈ R d is called a (δ, ϵ)-Goldstein stationary point of f (•) if it holds that min{∥g∥ : g ∈ ∂ δ f (x)} ≤ ϵ.Recent work [13, 26, 28] has shown that it is possible to find a (δ, ϵ)-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 ⊆ R d be the set on which Φ is differentiable, then R d \ Q is of measure zero. Recent work assumes they have access to the unbiased stochastic gradient estimator of the objective function for any x ∈ Q. In our setting, the unbiased gradient estimator of the composite function Φ(x) is J G (x; ζ)∇F (g(x); ξ), where J G is the Jacobian matrix of the function G(•; ζ). However, such an estimator is hard to obtain because the function value g(x) is an expectation.The randomized smoothing is a popular technique for nonsmooth analysis [36] and gradient-free optimization [29] . Concretely, given a Lipschitz function f and a uniform distribution P on a unit ball, we define its smoothed surrogate as f δ (x) = E u∼P [f (x + δu)], which has the following properties.Lemma 3.7 (Lin et al. [30, Proposition 2.3] ). Let f δ (x) = E u∼P [f (x + δu)] where P is a uniform distribution on a unit ball in ℓ 2 -norm. Suppose the function f is L-Lipschitz, then we have (a)|f δ (x) -f (x)| ≤ δL; (b) f δ (•) is differentiable everywhere and L-Lipschitz with cL √ dδ -1 -Lipschitz gradient, where c is some positive constant; (c) ∇f δ (x) ∈ ∂ δ f (x) for any x ∈ R d .Moreover, we consider the following unbiased gradient estimator of the smoothed surrogate function f δ (•), which can be obtained from two function query oracle calls on points uniformly sampled from a unit sphere [37] .Lemma 3.8 (Lin et al. [30, Lemma D.1]). Let f (x) = E[F (x; ξ)] be a L-Lipschitz function. We denote ι(x; u, ξ) ≜ d 2δ (F (x + δu; ξ) -F (x -δu; ξ))u,where u is uniformly sampled from a distribution on a unit sphere in R d space. Then, we haveE[ι(x; u, ξ)] = ∇f δ (x) and E[∥ι(x; u, ξ)∥ 2 ] ≤ 16 √ 2πdL 2 .4 Algorithms for Nonconvex Nonsmooth SCOIn 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 2: GFCOM + (x 0 , η, T, b f , b ′ f , b g , b ′ g , m) 1 for t = 0, 1, . . . , T -1 do 2 if t mod m = 0 then 3 Sample {ξ t,i , w t,i } b f i=1 and {ζ t,i } bg i=1 . 4 Generate G(x t ± δw t,j ; ζ t,i ) for every (i, j) ∈ [b g ] × [b f ]. 5 Let y t,j = 1 bg i∈[bg] G(x t + δw t,j ; ζ t,i ). 6 Let z t,j = 1 bg i∈[bg] G(x t -δw t,j ; ζ t,i ). 7 Let v t = 1 b f j∈[b f ] d 2δ (F (y t,j ; ξ t,j ) -F (z t,j ; ξ t,j ))w t,j . 8 else 9 Sample {ξ t,i , w t,i } b ′ f i=1 and {ζ t,i } b ′ g i=1 . 10 Generate G(x t ± δw t,j ; ζ t,i ) and G(x t-1 ± δw t,j ; ζ t,i ) for every (i, j) ∈ [b ′ g ] × [b ′ f ]. 11 Let y k,j = 1 b ′ g i∈[b ′ g ] G(x k + δw t,j ; ζ k,i ) for k ∈ {t -1, t}. 12 Let z k,j = 1 b ′ g i∈[b ′ g ] G(x k -δw t,j ; ζ k,i ) for k ∈ {t -1, t}. 13 Let q k = 1 b ′ f j∈[b ′ f ] d 2δ(F (y k,j ; ξ t,j ) -F (z k,j ; ξ t,j ))w t,j for k ∈ {t -1, t}.14Let v t = q t -q t-1 + v t-1 .15 end 16 Update x t+1 = x t -ηv t . 17 end 18 Return: x R where R is uniformly sampled from [T ].Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [No] Justification: We are clearing the code with internal compliance and will release it upon approval.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 estimatorEQUATIONwhere b f > 0 is the mini-batch size of the gradient estimator. By Lemma 3.8, the vector vt is an unbiased estimator of ∇Φ δ (x t ). Unfortunately, it is intractable to obtain the function values g(x t ± δw t,j ) because g(•) is an expectation of stochastic component functions G(•; ζ). To remedy this issue, we introduce auxiliary variables y t,j and z t,j to approximate the inner function values g(x t + δw t,j ) and g(x t -δw t,j ), respectively. In particular, the vectors y t,j and z t,j are mini-batch function estimators defined as followsEQUATIONwhere b g > 0 is the mini-batch size of the function estimator. Accordingly, we use these two variables to replace the function calls of g(•) in the gradient estimator v t of Eq. ( 2). The complete procedure of the GFCOM is presented in Algorithm 1.For the GFCOM + , we leverage the variance reduction technique to approximate ∇Φ δ (x t ). In particular, we consider the following hypothetical recursive gradient estimatorEQUATIONwhere qt and qt-1 are mini-batch gradient estimator defined as follows.qk = 1 b ′ f j∈[b ′ f ] d 2δ (F (g(x k + δw t,j ); ξ t,j ) -F (g(x k -δw t,j ); ξ t,j ))w t,j ,where b ′ f > 0 is the mini-batch size and k ∈ {t -1, t}. Compared with the mini-batch gradient estimator (2), the recursive gradient estimator (4) has been shown to achieve a sharper complexity bound in nonconvex optimization literature [17, 18, 31] . However, the gradient estimator is computationally intractable due to the unknown function g(•). Similar to the development of Algorithm 1, we define y t , z t to estimate the inner function values g(x t ± δw t,j ). We also introduce variables y t-1 , z t-1 to approximate the inner function values g(x t-1 ± δw t,j ) at the previous iteration. Then we define stochastic gradient estimators q t and q t-1 in terms of y t , y t-1 , z t and z t-1 .q k = 1 b ′ f j∈[b ′ f ] d 2δ (F (y k,j ; ξ t,j ) -F (z k,j ; ξ t,j ))w t,j ,for k ∈ {t -1, t}. We replace the minibatch gradient estimator qt and qt-1 in the recursive gradient estimator vt of Eq. ( 4) with the refined gradient estimators q t and q t-1 . The complete procedure of GFCOM + is presented in Algorithm 2.In this subsection, we consider the complexity analysis of the proposed algorithms introduced in Section 4.1. We assume that Φ(x 0 ) -Φ * ≤ R, where R > 0 is some constant.The following theorem shows the convergence rate of solving the Problem (1) with the GFCOM method presented in Algorithm 1. Theorem 4.1. Under Assumption 3.1, 3.3 and 3.4, running the GFCOM algorithm (Algorithm 1)with η ≤ δ/(cG f G g √ d)where c > 0 is some constant, then the output x R satisfiesEQUATIONUsing Theorem 4.1 with the parameter settingT = Θ G f G g √ dR δϵ 2 + G 2 f G 2 g √ d ϵ 2 , b f = Θ dG 2 f G 2 g ϵ 2 and b g = Θ d 2 G 2 f σ 2 0 δ 2 ϵ 2 ,we obtain the following oracle complexity result for Algorithm 1. Corollary 4.2. Under Assumption 3.1, 3.3 and 3.4, the GFCOM algorithm (Algorithm 1) requires at mostO d 3.5 G 5 f G 3 g σ 2 0 Rδ -3 ϵ -6 + d 3.5 G 6 f G 4 g σ 2 0 δ -2 ϵ -6stochastic zeroth-order function query calls to obtain a (δ, ϵ)-Goldstein stationary point of Φ.After giving the complexity bound of GFCOM in Corollary 4.2, we now consider the convergence analysis of GFCOM + . We will show that it enjoys a sharper complexity bound due to the utilization of the recursive gradient estimator. The following theorem shows the convergence rate of solving Problem (1) with the GFCOM + (Algorithm 2). Theorem 4.3. Under Assumption 3.1, 3.3 and 3.4, running the GFCOM + algorithm (Algorithm 2)with η = δ/(2cG f G g √ d), b ′ f = Θ(dG f G g ϵ -1 ) and m = Θ(G f G g ϵ -1), then the output x R satisfiesE ∥∇Φ δ (x R )∥ 2 = O √ dG f G g R δT + √ dG 2 f G 2 g T + dG 2 f G 2 g b f + d 2 G 2 f σ 2 0 δ 2 b g + d 2 G 2 f σ 2 0 δ 2 b ′ g . Algorithm 3: WS-GFCOM(x 0 , η 0 , T 0 , b g,0 , η, T, b f , b g , b ′ f , b ′ g , m) 1 Let x 1 = GFCOM(x 0 , η 0 , T 0 , 1, b g,0 ). 2 Option I (WS-GFCOM 2 ): x 2 = GFCOM(x 1 , η, T, b f , b g ). 3 Option II (WS-GFCOM + ): x 2 = GFCOM + (x 1 , η, T, b f , b ′ f , b g , b ′ g , m). 4 Return: x 2 .Using Theorem 4.3 with the parameter settingT = Θ √ dG f G g R δϵ 2 + √ dG 2 f G 2 g ϵ 2 , b f = Θ dG 2 f G 2 g ϵ 2 , b g = b ′ g = Θ d 2 G 2 f σ 2 0 δ 2 ϵ 2 ,we obtain the following oracle complexity result for Algorithm 2. Corollary 4.4. Under Assumption 3.1, 3.3 and 3.4, the GFCOM + algorithm (Algorithm 2) requires at mostO d 3.5 G 4 f G 2 g σ 2 0 Rδ -3 ϵ -5 + d 3.5 G 5 f G 3 g σ 2 0 δ -2 ϵ -5stochastic zeroth-order function query calls to obtain a (δ, ϵ)-Goldstein stationary point of Φ.For both Theorem 4.1 and 4.3, we take c = 1 according to Lemma 8 of Duchi et al. [36] .In Algorithm 2, we only apply the variance reduction technique to the outer function f (•) to accelerate our algorithm. In contrast, existing methods [2, 7, 22] for nonconvex smooth SCO also apply the technique on the inner function estimator to obtain an improved complexity bound. Here we briefly discuss the cause that leads to such a difference. For smooth optimization, the main intuition of the variance reduction technique is to establish a connection between the bound of the meansquare error term E ∥v t -∇Φ(x t ))∥2 and the expected distance of iterates at successive iterationsE[∥x t -x t-1 ∥ 2 ], which diminishes asymptotically. In our algorithm, we exploit the randomized smoothing with perturbed iterates x t ± δw t,j to approximate the gradient of the smoothed surrogate function Φ δ (x t ). If we apply the variance reduction to the inner function estimator, the meansquare error E[∥v t -∇Φ δ (x t ))∥ 2 ] is bounded by the expected distance of the perturbed iterates at successive iterations E[∥x t -x t-1 ± δ(w t,j -w t-1,j )∥ 2 ], which does not vanish asymptotically. 
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; ζ) is convex for any given ζ, and the solution setX * = arg min x∈R d Φ(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 (δ, ϵ)-Goldstein stationary point of the problem, we propose a two-phase gradient-free stochastic method called warm-started GFCOM (WS-GFCOM) in Algorithm 3. The intuition is that we use the GFCOM method to get a sufficiently small sub-optimality in the first phase, and then we apply the proposed methods in Section 4.1 to 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 it can achieve optimal convergence rate in terms of the sub-optimality of function value gap given the access to the exact function value g(x) [39] .In this subsection, we consider the complexity analysis of the proposed WS-GFCOM method. Let R ≜ min x∈X * ∥x -x 0 ∥. We characterize the convergence rate of the WS-GFCOM method for the convex nonsmooth SCO problem at the first phase with the following theorem. = Θ R/(G f G g √ dT 0 ) , T 0 = Θ dG 2 f G 2 g R2 ρ -2 , b g,0 = Θ G 2 f σ 2 0 ρ -2 and δ = Θ ρG -1 f G -1 g , then the output x 1 satisfies E[Φ(x 1 ) -Φ * ] ≤ ρ.In addition, the total zerothorder stochastic oracle complexity is at mostO dG 4 f G 2 g σ 2 0 R2 ρ -4 .Theorem 5.2 implies that the initial suboptimality at the beginning of the second phase is bounded by ρ. Consequently, the total complexity of WS-GFCOM2 (Algorithm 3 with Option I) is bounded byO dG 4 f G 2 g σ 2 0 R2 ρ -4 + d 3.5 G 5 f G 3 g σ 2 0 ρδ -3 ϵ -6 + d 3.5 G 6 f G 4 g σ 2 0 δ -2 ϵ -6. An appropriate choice of ρ leads to the following oracle complexity of Algorithm 3 with Option I. O d 3 G 4 f G 2 g σ 2 0 R0.4 δ -2.4 ϵ -4 + d 3.5 G 5 f G 3 g σ 2 0δ -2 ϵ -5 stochastic zeroth-order function query calls to obtain a (δ, ϵ)-Goldstein stationary point of Φ. 
experiments: 
 We compare the proposed methods GFCOM and GFCOM + with a Kiefer-Wolfowitz style zeroth-order baseline method [2, 40] . In particular, the baseline gradient estimator is defined asv t = 1 b f j∈[b f ] d 2δ F (y t,j ; ξ t,j ) -F (z t,j ; ξ ′ t,j ) ,where y t,j and z t,j are function estimators defined in Eq. (3). ξ t,j and ξ ′ t,j are independent random variables. We test all the methods on the nonconvex penalized risk-averse portfolio management problem and a reinforcement learning (RL) problem. We set δ = 0.1 for the GFCOM and GFCOM + methods.We consider the portfolio management problem with capped-ℓ 1 regularizer [41] . Let x denote the investment quantity corresponding to N assets and r t ∈ R N denote the returns of N assets at timestamp t. We can formulate the portfolio management problem as the following nonsmooth compositional optimization problemEQUATIONwhere β(x) = λ N i=1 min{|x i |, α} and λ, α > 0 are tunable hyperparameters. Specifically, the inner function G(x; ξ) and outer function F (w; ζ) can be formulated asG(x; ξ) = [x 1 , . . . , x N , ⟨r ξ , x⟩] ⊤ and F (w; ζ) = -⟨r ζ , w [N ] ⟩ + (⟨r ζ , w [N ] ⟩ -w N +1 ) 2 + β(x).Both random variables ξ and ζ are uniformly sampled from {1, . . . , T }. We choose λ = 10 -5 and α = 2 in our experiments. The goal of the Problem ( 6) is to maximize the return while controlling the variance of the portfolio.We compare all the methods on 6 different portfolio datasets formed on Size and Operating Profitability 2 . For all algorithms, we tune the stepsize among {1 × 10 -5 , 3 × 10 -5 , . . . , 1 × 10 -3 , 3 × 10 -3 }. f = 10 for the GFCOM + algorithm. Figure 1 shows that the GFCOM + algorithm converges much faster than the GFCOM and the baseline method across all datasets.We demonstrate an experiment on RL and verify the effectiveness of the proposed methods on value function evaluation. Let V π (s) be the value function of a state s under a policy π for all state s ∈ S where |S| = n. Let r s ′ ,s be the reward transition from s ′ to s, and γ > 0 is a discounting factor. Furthermore, we assume that the value of each state can be parameterized as a linear map of some feature map ψ s ∈ R d of the state s such that V π (s) = ⟨ψ s , w⟩. Then we formulate the RL problem as a Bellman residual minimization problemmin w∈R d n s=1 h ⟨ψ s , w⟩ - s ′ P ss ′ (r s,s ′ + γ⟨ψ s ′ , w⟩) ,where P ss ′ is the probability transition matrix and h(x) = 1-exp(-|x|/σ) is a nonconvex nonsmooth loss which is more robust to adversarial outliers than the squared loss [42, 43] . Specifically, the inner function G(x; ξ) and outer function F (w; ζ) can be formulated as G(w; ξ) = [⟨ψ 1 , w⟩, r 1,ξ1 + γ⟨ψ ξ1 , w⟩, . . . , ⟨ψ n , w⟩, r n,ξn + γ⟨ψ ξn , w⟩] ⊤ andF (z; ζ) = h(z 2ζ -z 2ζ+1 ).In the above formulation, each ξ i is uniformly sampled from {P i1 , . . . , P in } and ζ is uniformly sampled from {1, . . . , T }. We follow a similar experiment setup by Yuan et al. [22] . Specifically, we generate a Markov decision process with different numbers of states n ∈ {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, 1]. In terms of hyperparameter setting, we choose b f = b g = 100 for all algorithms. In addition, we set b ′ f = 10, b ′ g = 100 and m = b f /b ′ f = 10 for the GFCOM + algorithm. For other hyperparameters, we use the same setting for the portfolio management problem. The experimental results in Figure 2 show that the GFCOM + significantly outperforms other methods.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 to a 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, or as supplemental material. 
conclusion: 
 In this work, we propose novel zeroth-order algorithms for nonconvex nonsmooth stochastic compositional optimization. We present the non-asymptotic convergence rate of the proposed algorithms for obtaining a (δ, ϵ)-Goldstein point of the problem. Furthermore, we extend our methods with a warmstart 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.The appendix is organized as follows. Section A introduces supporting lemmas that are essential for the analysis of the proposed gradient-free SCO methods. Section B proves the convergence rate of the GFCOM method introduced in Section 4. Section C proves the convergence rate of the GFCOM + method which enjoys a better function oracle call complexity. Section D provides the convergence analysis of the WS-GFCOM 2 and WS-GFCOM + proposed in Section 5.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Throughout the work, we define the variable g t (x) = 1 bg i∈[bg] G(x; ζ t,i ) for the GFCOM algorithm, and we denoteEQUATIONfor the GFCOM + method. Now we introduce an important lemma which is useful for the analysis of both GFCOM and GFCOM + algorithms. Lemma A.1. Under Assumption 3.1 and 3.3, for both Algorithms 1 and 2 it holds thatE[(f • g) δ (x t+1 ) -(f • g) δ (x t )] ≤ - η 2 E ∥∇(f • g) δ (x t )∥ 2 - η 2 - cη 2 G f G g √ d 2δ E ∥v t ∥ 2 + η 2 E ∥v t -∇(f • g) δ (x t )∥ 2 .Proof. From the smoothness of Φ δ = (f • g) δ , we have(f • g) δ (x t+1 ) -(f • g) δ (x t ) ≤⟨∇(f • g) δ (x t ), x t+1 -x t ⟩ + cG f G g √ d 2δ ∥x t+1 -x t ∥ 2 = -η[⟨∇(f • g) δ (x t ), v t ⟩] + cη 2 G f G g √ d 2δ ∥v t ∥ 2 = - η 2 ∥∇(f • g) δ (x t )∥ 2 - η 2 - cη 2 G f G g √ d 2δ ∥v t ∥ 2 + η 2 ∥v t -∇(f • g) δ (x t )∥ 2 .Taking expectations on both sides of the inequality, we get the desired result.Before giving the analysis of the convergence rate of Algorithm 1, we first present the bound of the mean-square error term E ∥v t -∇Φ δ (x t )∥ 2 .Lemma B.1. Under Assumption 3.1 and 3.3, for Algorithm 1 it holds thatE ∥v t -∇Φ δ (x t )∥ 2 ≤ 2d 2 G 2 f σ 2 0 δ 2 b g + 32 √ 2πdG 2 f G 2 g b f Proof. Recall that v t = 1 b f j∈[b f ] d 2δ (F (y t,j ; ξ t,j ) -F (z t,j ; ξ t,j)), we haveE ∥v t -∇Φ δ (x t )∥ 2 ≤2E    v t - 1 b f j∈[b f ] d 2δ (F (g(x t + δw t,j ); ξ t,j ) -F (g(x t -δw t,j ); ξ t,j )) 2    + 2E    1 b f j∈[b f ] d 2δ (F (g(x t + δw t,j ); ξ t,j ) -F (g(x t -δw t,j ); ξ t,j )) -∇(f • g) δ (x t ) 2    ≤2   d 2 2δ 2 b f j∈[b f ] E ∥F (g(x t + δw t,j ); ξ t,j ) -F (g t (x t + δw t,j ); ξ t,j )∥ 2 + d 2 2δ 2 b f j∈[b f ] E ∥F (g(x t -δw t,j ); ξ t,j ) -F (g t (x t -δw t,j ); ξ t,j )∥ 2   + 32 √ 2πdG 2 f G 2 g b f ≤ 2d 2 G 2 f σ 2 0 δ 2 b g + 32 √ 2πdG 2 f G 2 g b f .The first inequality is due to ∥a + b∥ η 2 E[∥∇(f • g) δ (x t )∥ 2 ] ≤ E[(f • g) δ (x t ) -(f • g) δ (x t+1 )] + η 2 E[∥v t -∇(f • g) δ (x t )∥ 2 ].Sum the above inequality from t = 0 to T -1 and divide both sides by ηT 2 , we have1 T T -1 t=0 E ∥∇(f • g) δ (x t )∥ 2 ≤ 2cG f G g √ dE [(f • g) δ (x 0 ) -(f • g) δ (x T )] δT + 32 √ 2πdG 2 f G 2 g b f + 2d 2 G 2 f σ 2 0 δ 2 b g .In addition, by Lemma 3.7, we haveE [(f • g) δ (x 0 ) -(f • g) δ (x T )] ≤ E[(f • g)(x 0 ) -(f • g)(x T )] + 2G f G g δ.Combining the last two inequalities, we get the desired result.Proof. The total zeroth-order oracle calls can be bounded byO(T b f b g ) =O G f G g √ dR δϵ 2 + G 2 f G 2 g √ d ϵ 2 • dG 2 f G 2 g ϵ 2 • d 2 G 2 f σ 2 0 δ 2 ϵ 2 =O d 3.5 G 5 f G 3 g σ 2 0 R δ 3 ϵ 6 + d 3.5 G 6 f G 4 g σ 2 0 δ 2 ϵ 6 .In this section, we consider the formal proof of the convergence rate of the GFCOM + method. First, we introduce the following lemma to bound the mean-square error between the recursive gradient estimator and the gradient of the surrogate function.Lemma C.1. Let n t = ⌊t/m⌋ m. Under Assumption 3.1 and 3.3, for Algorithm 2 it holds thatE ∥v t -∇(f • g) δ (x t )∥ 2 ≤ 10d 2 G 2 f G 2 g η 2 δ 2 b ′ f t i=nt E ∥v i ∥ 2 + 10md 2 G 2 f σ 2 0 δ 2 b ′ f b ′ g + 32 √ 2πdG 2 f G 2 g b f + 2cd 2 G 2 f σ 2 0 δ 2 b g + 2cd 2 G 2 f σ 2 0 δ 2 b ′ g .Proof. By ∥a + b∥ 2 ≤ 2 ∥a∥ 2 + 2 ∥b∥ 2 , we can infer thatE ∥v t -∇(f • g) δ (x t )∥ 2 ≤2E ∥v t -∇(f • g t ) δ (x t )∥ 2 + 2E ∥∇(f • g t ) δ (x t ) -∇(f • g) δ (x t )∥ 2 .To bound the first term of R.H.S., we haveE[∥v t -∇(f • g t ) δ (x t )∥ 2 ] =E   1 b ′ f j∈[b ′ f ] d 2δ (F (y t,j ; ξ t,j )-F (z t,j ; ξ t,j ))w t,j - d 2δ (F (y t-1,j ; ξ t,j )-F (z t-1,j ; ξ t,j ))w t,j +v t-1 -∇(f • g t ) δ (x t )∥ 2 =E   1 b ′ f j∈[b ′ f ] d 2δ (F (y t,j ; ξ t,j )-F (z t,j ; ξ t,j ))w t,j - d 2δ (F (y t-1,j ; ξ t,j )-F (z t-1,j ; ξ t,j ))w t,j -(∇(f • g t ) δ (x t ) -∇(f • g t-1 ) δ (x t-1 ))∥ 2 + E ∥v t-1 -∇(f • g t-1 ) δ (x t-1 )∥ 2 ≤ 1 b ′2 f j∈[b ′ f ] E d 2δ(F (y t,j ; ξ t,j )-F (z t,j ; ξ t,j ))w t,j -d 2δ (F (y t-1,j ; ξ t,j )-F (z t-1,j ; ξ t,j ))w t,j2+ E ∥v t-1 -∇(f • g t-1 ) δ (x t-1 )∥ 2 .The second equality follows from Lemma 3.8. The last inequality is due toE[∥x -E[x]∥ 2 ] ≤ E[∥x∥ 2 ]. Observe that E d 2δ (F (y t,j ; ξ t,j ) -F (z t,j ; ξ t,j ))w t,j - d 2δ (F (y t-1,j ; ξ t,j ) -F (z t-1,j ; ξ t,j ))w t,j 2 ≤5E d 2δ (F (g(x t + δw t,j ); ξ t,j ) -F (g(x t -δw t,j ); ξ t,j )- (F (g(x t-1 + δw t,j ); ξ t,j ) -F (g(x t-1 -δw t,j ); ξ t,j )))w t,j ∥ 2 + 5E d 2δ (F (g(x t + δw t,j ); ξ t,j ) -F (y t,j ; ξ t,j ))w t,j 2 + 5E d 2δ (F (g(x t -δw t,j ); ξ t,j ) -F (z t,j ; ξ t,j ))w t,j 2 + 5E d 2δ (F (g(x t-1 + δw t,j ); ξ t,j ) -F (y t-1,j ; ξ t,j ))w t,j 2 + 5E d 2δ (F (g(x t-1 -δw t,j ); ξ t,j ) -F (z t-1,j ; ξ t,j ))w t,j ≤ 5d 2 G 2 f G 2 g δ 2 E ∥x t -x t-1 ∥ 2 + 5d 2 G 2 f σ 2 0 δ 2 b ′ g = 5d 2 G 2 f G 2 g η 2 δ 2 E ∥v t-1 ∥ 2 + 5d 2 G 2 f σ 2 0 δ 2 b ′ g .The first inequality is due to∥a 1 + • • • + a n ∥ 2 ≤ n ∥a 1 ∥ 2 + • • • + n ∥a n ∥ 2 .The second inequality is due to the Lipschitzness of both inner and outer functions with Assumption 3.3. Consequently, one hasE ∥v t -∇(f • g t ) δ (x t )∥ 2 ≤ 5d 2 G 2 f G 2 g η 2 δ 2 b ′ f E ∥v t-1 ∥ 2 + 5d 2 G 2 f σ 2 0 δ 2 b ′ f b ′ g + E ∥v t-1 -∇(f • g t-1 ) δ (x t-1 )∥ 2 ≤ 5d 2 G 2 f G 2 g η 2 δ 2 b ′ f t i=nt E ∥v i ∥ 2 + 5md 2 G 2 f σ 2 0 δ 2 b ′ f b ′ g + 16 √ 2πdG 2 f G 2 g b f .The last inequality follows from Lemma 3.8. In addition, for t mod m = 0 we can boundE ∥∇(f • g t ) δ (x t ) -∇(f • g) δ (x t )∥ 2 =E E u d δ ((f • g t )(x t + δu) -(f • g)(x t + δu)) u 2 ≤ d 2 δ 2 E u ∥(f • g t )(x t + δu) -(f • g)(x t + δu)∥ 2 ∥u∥ 2 ≤ cd 2 G 2 f σ 2 0 δ 2 b g .The last inequality follows from the Lipschitzness of f and Assumption 3.3. Similarly, for t mod m ̸ = 0 we can boundE ∥∇(f • g t ) δ (x t ) -∇(f • g) δ (x t )∥ 2 ≤ cd 2 G 2 f σ 2 0 δ 2 b ′ g .Putting everything together, we get the desired bound.We present the formal proof of Theorem 4.3 and Corollary 4.4 below.Proof. Rearrange the terms in Lemma A.1, sum t from 0 to T -1, and divide both sides by ηT 2 ,1 T T -1 t=0 E ∥∇(f • g) δ (x t )∥ 2 ≤ 2E [(f • g) δ (x 0 ) -2(f • g) δ (x T )] ηT - 1 T 1 - cηG f G g √ d δ T -1 i=0 E ∥v i ∥ 2 + 1 T T -1 t=0 E ∥v t -∇(f • g) δ (x t )∥ 2 ≤ 2E [(f • g) δ (x 0 ) -2(f • g) δ (x T )] ηT - 1 T 1 - cηG f G g √ d δ - 10md 2 G 2 f G 2 g η 2 δ 2 b ′ f T -1 i=0 E ∥v i ∥ 2 + 10md 2 G 2 f σ 2 0 δ 2 b ′ f b ′ g + 32 √ 2πdG 2 f G 2 g b f + 2cd 2 G 2 f σ 2 0 δ 2 b g + 2cd 2 G 2 f σ 2 0 δ 2 b ′ g .The last inequality follows from Lemma C.1. If we choose hyperparameters as followsη = δ 2cG f G g √ d , b ′ f = Θ dG f G g ϵ , m = Θ G f G g ϵ ,Then we can deduce that 1 -cηG f Gg √ d δ - 10md 2 G 2 f G 2 g η 2 δ 2 b ′ f ≤ 0. By Lemma 3.7, we have E [(f • g) δ (x 0 ) -(f • g) δ (x T )] ≤ E[(f • g)(x 0 ) -(f • g)(x T )] + 2G f G g δ.Therefore, we obtain the following resultE ∥∇Φ δ (x R )∥ 2 = O √ dG f G g R δT + √ dG 2 f G 2 g T + dG 2 f G 2 g b f + d 2 G 2 f σ 2 0 δ 2 b g + d 2 G 2 f σ 2 0 δ 2 b ′ g . C.2 Proof of Corollary 4.4Proof. The total zeroth-order oracle calls can be bounded byO(T b ′ f b ′ g + T b f b g /m) =O √ dG f G g R δϵ 2 + √ dG 2 f G 2 g ϵ 2 • dG f G g ϵ • d 2 G 2 f σ 2 0 δ 2 ϵ 2 =O d 3.5 G 4 f G 2 g σ 2 0 R δ 3 ϵ 5 + d 3.5 G 5 f G 3 g σ 2 0 δ 2 ϵ 5 .In this section, we present the formal proof of theorems presented in Section 5.Proof. Since G(•; ζ) is convex function, g t (•) is also convex. Using the result of Section 3.2.4 of [38] and Assumption 5.1, we can deduce that f • g t is a convex function. Let x * = arg min x (f • g) δ (x), then we haveE[(f • g t ) δ (x t ) -(f • g t ) δ (x * )] ≤E[⟨∇(f • g t ) δ (x t ), x t -x * ⟩] =E d 2δ (F (g t (x t + δu), ξ t ) -F (g t (x t -δu), ξ t )), x t -x * ≤ 1 η 0 E [⟨x t -x t+1 , x t -x * ⟩] = 1 2η 0 E ∥x t -x * ∥ 2 -∥x t+1 -x * ∥ 2 + ∥x t -x t+1 ∥ 2 ≤ 1 2η 0 E ∥x t -x * ∥ 2 -∥x t+1 -x * ∥ 2 + 8 √ 2πdG 2 f G 2 g η 0 .The first inequality follows from the convexity of f • g t . The last inequality is due to Lemma 3.8.Observe that for ∀x ∈ R d ,|(f • g) δ (x) -(f • g t ) δ (x)| =|E u [(f • g)(x + δu)] -E u [(f • g t )(x + δu)]| =|E u [(f • g)(x + δu) -(f • g t )(x + δu)]| ≤E u [|(f • g)(x + δu) -(f • g t )(x + δu)|] ≤ c 1 G f σ 0 b g,0 ,where c 1 is some constant. The second equality is due to the linearity of expectations. The last inequality follows from Assumption 3.3 and Lipschitzness of f . Consequently, we haveE[(f • g) δ (x 1 ) -(f • g) δ (x * )] ≤ R2 2η 0 T 0 + 8 √ 2πdG 2 f G 2 g η 0 + 2c 1 G f σ 0 b g,0 ≤ 12 RG f G g √ d √ T 0 + 2c 1 G f σ 0 b g,0 .By Lemma 3.7, we haveE [(f • g) δ (x 1 ) -(f • g) δ (x * )] ≤ E[(f • g)(x 1 ) -(f • g)(x * )] + 2G f G g δ. Consequently, one has E[(f • g) δ (x 1 ) -(f • g) δ (x * )] ≤ 12 RG f G g √ d √ T 0 + 2c 1 G f σ 0 b g,0 + 2G f G g δ.To obtainE[(f • g)(x 1 ) -(f • g)(x * )] ≤ ρ, we choose η 0 = R G f G g √ dT 0 , T 0 = Θ R2 G 2 f G 2 g d ρ 2 , b g,0 = Θ G 2 f σ 2 0 ρ 2 , δ = Θ ρ G f G g . D.2 Proof of Corollary 5.3Proof. The total stochastic function oracle calls can be bounded byO (T b f b g + T 0 b g,0 ) =O G f G g √ d(ρ + G f G g δ) δϵ 2 • dG 2 f G 2 g ϵ 2 • d 2 G 2 f σ 2 0 δ 2 ϵ 2 + d R2 G 4 f G 2 g σ 2 0 ρ 4 =O d 3.5 G 5 f G 3 g σ 2 0 ρ δ 3 ϵ 6 + d 3.5 G 6 f G 4 g σ 2 0 δ 2 ϵ 6 + d R2 G 4 f G 2 g σ 2 0 ρ 4 =O d 3 R0.4 G 4.8 f G 2.8 g σ 2 0 δ 2.4 ϵ 4.8 + d 3.5 G 6 f G 4 g σ 2 0δ 2 ϵ 6 .Proof. The total stochastic function oracle calls can be bounded byO T b ′ f b ′ g + T b f b g /m + T 0 b g,0 =O G f G g √ d(ρ + G f G g δ) δϵ 2 • dG f G g ϵ • d 2 σ 2 0 G 2 f δ 2 ϵ 2 + d R2 G 4 f G 2 g σ 2 0 ρ 4 =O d 3.5 G 4 f G 2 g σ 2 0 ρ δ 3 ϵ 5 + d 3.5 G 5 f G 3 g σ 2 0 δ 2 ϵ 5 + d R2 G 4 f G 2 g σ 2 0 ρ 4 =O d 3 R0.4 G 4 f G 2 g σ 2 0 δ 2.4 ϵ 4 + d 3.5 G 5 f G 3 g σ 2 0 δ 2 ϵ 5 .NeurIPS Paper ChecklistJustification: There are no potential positive or 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 societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).http://mba.tuck.dartmouth.edu/pages/faculty/ken.french/data_library.html 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

The following are minor points: 
* 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. 
* L118: \mathbb{B}(x, \delta) should be \mathbb{B}_\delta(x), according to L93. 
* 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. 
* 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.
questions: questions: See above.
limitations: limitations: See above.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 


Reference.

[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.
questions: questions: Please see the weakness section.
limitations: limitations: No significant limitations in this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: * The technical novelty of this work is limited, as the proposed algorithms are mostly based on SGFM [1]. 
* 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). 
* 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. 

[1] Lin et al. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. NeurIPS, 2022.
questions: 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}))$. 
* 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? 

[1] Lin et al. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. NeurIPS, 2022. 

[2] Yuan et al. Efficient smooth non-convex stochastic compositional optimization via stochastic recursive gradient descent. NeurIPS, 2019. 

[3] Zhang and Xiao. A stochastic composite gradient method with incremental variance reduction. NeurIPS, 2019.
limitations: limitations: See above
paper_summary: paper_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.

I did not read all the details of the proof of the variance reduced algorithm and the convex analysis.
strength_weakness: strength_weakness: 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.

The value of $c$ should be given to actually implement the algorithm.
questions: 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?

Are the random variables $\xi$ and $\zeta$ independent? If yes it should probably be stated.

This 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.

Table 1: what is WS-GFCOM?

This 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.

Section 6: what is the underlying compositional structure? What are the random variables?

Equality (2) is extremely misleading as a different expression is used in the algorithms and proofs.
limitations: limitations: Section 4.2, what is the value of $c$. Without this the algorithm cannot be implemented.

The convex section is probably of more limited interest than the rest.

The 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?

Comments: title: Answer to rebuttal
comment: We are glad that our rebuttal helped address your concerns. Thank you for raising the score!
Thank you for the response. I will raise my score to 5.
Thank you for raising our score! We are happy to hear that we have addressed your concerns.
Thanks for your detailed response! The concerns regarding the correctness of this paper have been fully addressed. The results of this work are indeed valuable. I will increase my score to 5.
Thanks for your careful and detailed reply. We would like to address your questions as follows. 

**Q1:** I have some concerns regarding the proof of Lemma B.1 (Line 411). Specifically, where does $g_t$ come from in the second inequality? Is this a mistake? If it should be instead, then the expression in the expectation would be 0, i.e., $E[\|F(g(x_t + \delta w_{t,j});\xi_{t,j})-F(g(x_t + \delta w_{t,j}); \xi_{t,j})\|^2]=0$. Is this a mistake? 

**A1:** Please note that we have defined $g_t(\cdot)$ for GFCOM (Algorithm 1) at the beginning of Appendix A (line 399), that is
$$g_t(x) = \frac{1}{b_g} \sum_{i \in [b_g]}G(x; \zeta_{t,i})$$
which is indeed different from
$$g(x) = E_\zeta[G(x;\zeta)].$$
In the proof of Lemma B.1, the notation $g_t(\cdot)$ is **not** a mistake.
Therefore, the terms 

$F(g(x_t + \delta w_{t,j}); \xi_{t,j})$  and   $F(g_t(x_t + \delta w_{t,j}); \xi_{t,j}) $

are **different**.
The expression $E[\|F(g(x_t + \delta w_{t,j}); \xi_{t,j})-F(g_t(x_t + \delta w_{t,j}); \xi_{t,j})\|^2]$ is also **not** a mistake and cannot be replaced by 
$E[\|F(g(x_t + \delta w_{t,j}); \xi_{t,j})-F(g(x_t + \delta w_{t,j}); \xi_{t,j})\|^2].$

**Q2:** I think that the authors may omit some steps. Could the authors provide a more detailed and correct analysis of Lemma B.1?

**A2:** Recall that we have defined $g_t(x) = \frac{1}{b_g} \sum_{i \in [b_g]}G(x; \zeta_{t, i})$ for the GFCOM method in line 399, we can simplify $y_{t,j}$ and $z_{t,j}$ in Eq.(3) (below line 157) as 

$y_{t,j} = g_t(x_t + \delta w_{t,j})$ and  $z_{t,j} = g_t(x_t - \delta w_{t,j}).$

Consequently, we can rewrite $v_t$ (Line 6 in Algorithm 1) as
$$v_t  = \frac{1}{b_f} \sum_{j \in [b_f]} \frac{d}{2 \delta}(F(g_t(x_t + \delta w_{t,j}); \xi_{t,j}) - F(g_t(x_t - \delta w_{t,j}); \xi_{t,j})) w_{t,j}.$$

Now we can bound the gradient estimation error as 
$$E[\lVert v_t - \nabla \Phi_{\delta} (x_t) \rVert^2] \leq  2 E\Big[ \Big\lVert v_t - \frac{1}{b_f} \sum_{j \in [b_f]} \frac{d}{2 \delta} (F(g(x_t + \delta w_{t,j}); \xi_{t,j}) - F(g(x_t - \delta w_{t,j});\xi_{t,j})) \Big\rVert^2 \Big] + 2 E \Big[ \Big\lVert \frac{1}{b_f} \sum_{j \in [b_f]} \frac{d}{2 \delta} (F(g(x_t + \delta w_{t,j}); \xi_{t,j}) - F(g(x_t - \delta w_{t,j});\xi_{t,j})) - \nabla (f \circ g)_{\delta}(x_t) \Big\rVert^2 \Big] ,$$
where the inequality follows the fact $\lVert a + b\rVert^2 \leq 2 \lVert a \rVert^2 + 2\lVert b\rVert^2$.
For the first term on the right-hand side, we have
$$
\begin{aligned}
& 2 E\Big[ \Big\lVert v_t - \frac{1}{b_f} \sum _{j \in [b_f]} \frac{d}{2 \delta} (F(g(x _t + \delta w _{t,j}); \xi _{t,j}) - F(g(x _t - \delta w _{t,j});\xi _{t,j})) \Big\rVert^2 \Big] \\\\
 \leq & 2 \Big(\frac{d^2}{2 \delta^2 b _f} \sum _{j \in [b _f]} E\Big[\Big\lVert F(g(x _t + \delta w _{t,j}); \xi _{t,j}) - F(g _t(x _t + \delta w _{t,j}); \xi _{t,j})\Big\rVert^2 \Big] + \frac{d^2}{2 \delta^2 b _f} \sum _{j \in [b_f]}E \Big[\Big\lVert F(g(x _t - \delta w _{t,j}); \xi _{t,j}) - F(g _t(x _t - \delta w _{t,j}); \xi _{t,j}\Big)^2\Big] \Big) \\\\
\leq & 2 \Big(\frac{G _f^2 d^2}{2 \delta^2 b_f} \sum _{j \in [b_f]} E \Big[\Big\lVert g(x _t + \delta w _{t,j}) - g _t(x _t + \delta w _{t,j}) \Big\rVert^2 \Big] + \frac{G _f^2 d^2}{2 \delta^2 b_f} \sum _{j \in [b_f]} E \Big[\Big\lVert g(x _t - \delta w _{t,j}) - g _t(x _t - \delta w _{t,j}) \Big\rVert^2 \Big]\Big)
\end{aligned}
$$
where first inequality is due to $\lVert a + b\rVert^2 \leq 2 \lVert a \rVert^2 + 2\lVert b\rVert^2$ and the second inequality follows Assumption 3.1.

Since $g_t(\cdot)$ is an unbiased estimator of $g(\cdot)$,  Assumption 3.3 implies

$E[\lVert g(x_t + \delta w_{t,j}) - g_t(x_t + \delta w_{t,j}) \rVert^2 ] \leq \frac{\sigma_0^2}{b_g}$ and $E[\lVert g(x_t - \delta w_{t,j}) - g_t(x_t - \delta w_{t,j}) \rVert^2 ] \leq \frac{\sigma_0^2}{b_g}$.

Combining the above two results, we have
$$2E\Big[ \Big\lVert v_t - \frac{1}{b_f} \sum_{j \in [b_f]} \frac{d}{2 \delta} (F(g(x_t + \delta w_{t,j}); \xi_{t,j}) - F(g(x_t - \delta w_{t,j});\xi_{t,j}))\Big\rVert^2 \Big] \leq \frac{2d^2 G_f^2 \sigma_0^2}{\delta^2 b_g}.$$
In addition, Lemma 3.8 implies
$$2 E \Big[ \Big\lVert \frac{1}{b_f} \sum_{j \in [b_f]} \frac{d}{2 \delta} (F(g(x_t + \delta w_{t,j}); \xi_{t,j}) - F(g(x_t - \delta w_{t,j});\xi_{t,j})) - \nabla (f \circ g)_{\delta}(x_t)\Big\rVert^2 \Big] \leq \frac{32 \sqrt{2 \pi} d G_f^2 G_g^2}{b_f}.$$
Putting everything together, we get the bound
$$E[\lVert v _t - \nabla \Phi _{\delta} (x _t) \rVert^2 ] \leq \frac{2 d^2 G_f^2 \sigma_0^2}{\delta^2 b _g}  + \frac{32 \sqrt{2 \pi} d G _f^2 G _g^2}{b _f},$$
which finishes the proof of Lemma B.1.

If you are still confused about our response, you are welcome to discuss it further!
Thank you for your detailed response, which has partially addressed my concerns. For the technical novelty, I have some further questions. 

**Q:** After reviewing Lemma B.1 and Lemma C.1, I find that the technical contribution in bounding the expected mean squared error may be limited, as the analysis using the Lipschitz continuity seems straightforward and easy. Additionally, I have some concerns regarding the proof of Lemma B.1 (Line 411). Specifically, where does $g_t$ come from in the second inequality? Is this a mistake? If it should be $g$ instead, then the expression in the expectation would be $0$, i.e., $E[\Vert F(g(\mathbf{x}\_t+\delta \mathbf{w}\_{t,j});\xi_{t,j}) - F(g(\mathbf{x}\_t+\delta \mathbf{w}\_{t,j});\xi\_{t,j})\Vert^2]=0$. Is this also a mistake? I think that the authors may omit some steps. Could the authors provide a more detailed and correct analysis of Lemma B.1?
I have read the authors response. Thanks.