Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

Introduction

In 1951, Robbins and Monro in their seminal work proposed a classical stochastic approximation (SA) algorithm for solving stochastic programming (SP) problems. This approach mimics the simplest gradient descent method by using noisy gradient information in place of the exact gradients, and possesses the “asymptotically optimal” rate of convergence for solving a class of strongly convex SP problems . However, it is usually difficult to implement the “asymptotically optimal” stepsize policy, especially in the beginning, so that the algorithms often perform poorly in practice (e.g., [39, Section 4.5.3]). An important improvement of the classical SA was developed by Polyak and Polyak and Juditsky , where longer stepsizes were suggested together with the averaging of the obtained iterates. Their methods were shown to be more robust with respect to the selection of stepsizes than the classical SA and also exhibit the “asymptotically optimal” rate of convergence for solving strongly convex SP problems. We refer to for an account of the earlier history of SA methods.

The last few years have seen some significant progress for the development of SA methods for SP. On one hand, new SA type methods are being introduced to solve SP problems which are not necessarily strongly convex. On the other hand, these developments, motivated by complexity theory in convex optimization , concerned the convergence properties of SA methods during a finite number of iterations. For example, Nemirovski et al. presented a properly modified SA approach, namely, mirror descent SA for solving general non-smooth convex SP problems. They demonstrated that the mirror descent SA exhibits an optimal ${\cal O}(1/\epsilon^{2})$ iteration complexity for solving these problems. This method has been shown in to be competitive to the widely-accepted sample average approximation approach (see, e.g., ) and even significantly outperform it for solving a class of convex SP problems. Similar techniques, based on subgradient averaging, have been proposed in . While these techniques dealt with non-smooth convex programming problems, Lan presented a unified optimal method for smooth, non-smooth and stochastic optimization, which explicitly takes into account the smoothness of the objective function (see also for discussions about strong convexity). However, note that convexity has played an important role in establishing the convergence of all these SA algorithms. To the best of our knowledge, none of existing SA algorithms can handle more general SP problems whose objective function is possibly nonconvex.

This paper focuses on the theoretical development of SA type methods for solving an important class of nonconvex SP problems. More specifically, we study the classical unconstrained nonlinear programming (NLP) problem given in the form of (e.g., )

for some parameter $\sigma\geq 0$. Observe that, by (1.2), $G(x_{k},\xi_{k})$ is an unbiased estimator of $\nabla f(x_{k})$ and, by (1.3), the variance of the random variable $\|G(x_{k},\xi_{k})-\nabla f(x_{k})\|$ is bounded. It is worth noting that in the standard setting for SP, the random vectors $\xi_{k}$, $k=1,2,\ldots$, are independent of each other (and also of $x_{k}$) (see, e.g., ). Our assumption here is slightly weaker since we do not need to assume $\xi_{k}$, $k=1,2,\ldots$, to be independent.

Our study on the aforementioned SP problems has been motivated by a few interesting applications which are briefly outlined as follows.

In many machine learning problems, we intend to minimize a regularized loss function $f(\cdot)$ given by

where either the loss function $L(x,\xi)$ or the regularization $r(x)$ is nonconvex (see, e.g., ).

Another important class of problems originate from the so-called endogenous uncertainty in SP. More specifically, the objective functions for these SP problems are given in the form of

where the support $\Xi(x)$ and the distribution function $P_{x}$ of the random vector $\xi$ depend on $x$. The function $f$ in (1.5) is usually nonconvex even if $F(x,\xi)$ is convex with respect to $x$. For example, if the support $\Xi$ does not depend on $x$, it is often possible to represent $dP_{x}=H(x)dP$ for some fixed distribution $P$. Typically this transformation results in a nonconvex integrand function. Other techniques have also been developed to compute unbiased estimators for the gradient of $f(\cdot)$ in (1.5) (see, e.g., ).

Secondly, in order to improve the large deviation properties and hence the reliability of the RSG method, we present a two-phase randomized stochastic gradient ($2$-RSG) method by introducing a post-optimization phase to evaluate a short list of solutions generated by several independent runs of the RSG method. We show that the complexity of the $2$-RSG method for computing an $(\epsilon,\Lambda)$-solution of problem (1.1), i.e., a point $\bar{x}$ such that ${\hbox{\rm Prob}}\{\|\nabla f(\bar{x})\|^{2}\leq\epsilon\}\geq 1-\Lambda$ for some $\epsilon>0$ and $\Lambda\in(0,1)$, can be bounded by

We further show that, under certain light-tail assumption about the ${\cal SFO}$, the above complexity bound can be reduced to

This paper is organized as follows. We introduce two stochastic first-order methods, i.e., the RSG and $2$-RSG methods, for nonconvex SP, and establish their convergence properties in Section 2. We then specialize these methods for solving a class of simulation-based optimization problems in Section 3. Some brief concluding remarks are also presented in Section 4.

If, in addition, $f(\cdot)$ is convex, then

Stochastic first-order methods

Our goal in this section is to present and analyze a new class of SA algorithms for solving general smooth nonlinear (possibly nonconvex) SP problems. More specifically, we present the RSG method and establish its convergence properties in Subsection 2.1, and then introduce the $2$-RSG method which can significantly improve the large-deviation properties of the RSG method in Subsection 2.2.

We assume throughout this section that Assumption A1 holds. In some cases, Assumption A1 is augmented by the following “light-tail” assumption.

It can be easily seen that Assumption A2 implies Assumption A1.b) by Jensen’s inequality.

The convergence of existing SA methods requires $f(\cdot)$ to be convex . Moreover, in order to guarantee the convexity of $f(\cdot)$, one often need to assume that the random variables $\xi_{k}$, $k\geq 1$, to be independent of the search sequence $\{x_{k}\}$. Below we present a new SA-type algorithm that can deal with both convex and nonconvex SP problems, and allow random noises to be dependent on the search sequence. This algorithm is obtained by incorporating a certain randomization scheme into the classical SA method.

A randomized stochastic gradient (RSG) method

Input: Initial point $x_{1}$, iteration limit $N$, stepsizes $\{\gamma_{k}\}_{k\geq 1}$ and probability mass function $P_{R}(\cdot)$ supported on $\{1,\ldots,N\}$.

Step . Let $R$ be a random variable with probability mass function $P_{R}$.

Step $k=1,\ldots,R$. Call the stochastic first-order oracle for computing $G(x_{k},\xi_{k})$ and set

A few remarks about the above RSG method are in order. Firstly, in comparison with the classical SA, we have used a random iteration count, $R$, to terminate the execution of the RSG algorithm. Equivalently, one can view such a randomization scheme from a slightly different perspective described as follows. Instead of terminating the algorithm at the $R$-th step, one can also run the RSG algorithm for $N$ iterations but randomly choose a search point $x_{R}$ (according to $P_{R}$) from its trajectory as the output of the algorithm. Clearly, using the latter scheme, we just need to run the algorithm for the first $R$ iterations and the remaining $N-R$ iterations are surpluses. Note however, that the primary goal to introduce the random iteration count $R$ is to derive new complexity results for nonconvex SP, rather than save the computational efforts in the last $N-R$ iterations of the algorithm. Indeed, if $R$ is uniformly distributed, the computational gain from such a randomization scheme is simply a factor of $2$. Secondly, the RSG algorithm described above is conceptual only because we have not specified the selection of the stepsizes $\{\gamma_{k}\}$ and the probability mass function $P_{R}$ yet. We will address this issue after establishing some basic convergence properties of the RSG method.

The following result describes some convergence properties of the RSG method.

Suppose that the stepsizes $\{\gamma_{k}\}$ and the probability mass function $P_{R}(\cdot)$ in the RSG method are chosen such that $\gamma_{k}<2/L$ and

where the expectation is taken with respect to $R$ and $\xi_{[N]}:=(\xi_{1},...,\xi_{N})$,

and $f^{*}$ denotes the optimal value of problem (1.1);

if, in addition, problem (1.1) is convex with an optimal solution $x^{*}$, then, for any $N\geq 1$,

where the expectation is taken with respect to $R$ and $\xi_{[N]}$, and

Summing up the above inequalities and re-arranging the terms, we obtain

Dividing both sides of the above inequality by $L\sum_{k=1}^{N}\left(\gamma_{k}-L\gamma_{k}^{2}/2\right)$ and noting that

which, in view of (2.5), clearly implies (2.4).

We now show that part b) holds. Display $\omega_{k}\equiv\|x_{k}-x^{*}\|$. First observe that, for any $k=1,\ldots,N$,

Moreover, in view of (1.8) and the fact that $\nabla f(x^{*})=0$, we have

Combining the above two relations, we obtain, for any $k=1,\ldots,N$,

where the last inequality follows from the convexity of $f(\cdot)$ and the fact that $\gamma_{k}\leq 2/L$. Summing up the above inequalities and re-arranging the terms, we have

where the last inequality follows from (2.7) and the fact that $\omega_{N+1}\geq 0$. The rest of the proof is similar to that of part a) and hence the details are skipped.

We now describe a possible strategy for the selection of the stepsizes $\{\gamma_{k}\}$ in the RSG method. For the sake of simplicity, let us assume that a constant stepsize policy is used, i.e., $\gamma_{k}=\gamma$, $k=1,\ldots,N$, for some $\gamma\in(0,2/L)$. Note that the assumption of constant stepsizes does not hurt the efficiency estimate of the RSG method. The following corollary of Theorem 1 is obtained by appropriately choosing the parameter $\gamma$.

Suppose that the stepsizes $\{\gamma_{k}\}$ are set to

where $D_{f}$ is defined in (2.5). If, in addition, problem (1.1) is convex with an optimal solution $x^{*}$, then

which together with (2.4) then imply (2.14). Relation (2.15) follows similarly from the above inequality (with $D_{f}$ replaced by $D_{X}$) and (2.6).

We now add a few remarks about the results obtained in Theorem 1 and Corollary 2. Firstly, as can be seen from (2.11), instead of randomly selecting a solution $x_{R}$ from $\{x_{1},\ldots,x_{N}\}$, another possibility would be to output the solution $\hat{x}_{N}$ such that

Thirdly, one possible drawback for the above RSG method is that one need to estimate $L$ to obtain an upper bound on $\gamma_{k}$ (see, e.g., (2.13)), which will also possibly affect the selection of $P_{R}$ (see (2.3)). Note that similar requirements also exist for some deterministic first-order methods (e.g., gradient descent and Nesterov’s accelerated gradient methods). While under the deterministic setting, one can somehow relax such requirements by using certain line-search procedures to enhance the practical performance of these methods, it is more difficult to devise similar line-search procedures for the stochastic setting, since the exact values of $f(x_{k})$ and $\nabla f(x_{k})$ are not available. It should be noted, however, that we do not need very accurate estimate for $L$ in the RSG method. Indeed, it can be easily checked that the RSG method exhibits an ${\cal O}(1/\sqrt{N})$ rate of convergence if the stepsizes $\{\gamma_{k}\}$ are set to

for any $q\in[1,\sqrt{N}]$. In other words, we can overestimate the value of $L$ by a factor up to $\sqrt{N}$ and the resulting RSG method still exhibits similar rate of convergence. A common practice in stochastic optimization is to estimate $L$ by using the stochastic gradients computed at a small number of trial points (see, e.g., ). We have adopted such a strategy in our implementation of the RSG method as described in more details in the technical report associated with this paper . It is also worth noting that, although in general the selection of $P_{R}$ will depend on $\gamma_{k}$ and hence on $L$, such a dependence is not necessary in some special cases. In particular, if the stepsizes $\{\gamma_{k}\}$ are chosen according to a constant stepsize policy (e.g., (2.13)), then $R$ is uniformly distributed on $\{1,\ldots,N\}$.

Fourthly, it is interesting to note that the RSG method allows us to have a unified treatment for both nonconvex and convex SP problems in view of the specification of $\{\gamma_{k}\}$ and $P_{R}(\cdot)$ (c.f., (2.3) and (2.13)). Recall that the optimal rate of convergence for solving smooth convex SP problems is given by

This bound has been obtained by Lan based on a stochastic counterpart of Nesterov’s method . Comparing (2.18) with the above bound, the RSG method possesses a nearly optimal rate of convergence, since the second term in (2.18) is unimprovable while the first term in (2.18) can be much improved. Moreover, as shown by Cartis et al. , the first term in (2.17) for nonconvex problems is also unimprovable for gradient descent methods. It should be noted, however that the analysis in applies only for gradient descent methods and does not show that the ${\cal O}(1/N)$ term is tight for all first-order methods.

Finally, observe that we can use different stepsize policy other than the constant one in (2.13). In particular, it can be shown that the RSG method with the following two stepsize policies will exhibit similar rates of convergence as those in Corollary 2.

Intuitively speaking, one may want to choose decreasing stepsizes which, according to the definition of $P_{R}(\cdot)$ in (2.3), can stop the algorithm earlier. On the other hand, as the algorithm moves forward and local information about the gradient gets better, choosing increasing stepsizes might be a better option. We expect that the practical performance of these stepsize policies will depend on each problem instance to be solved.

While Theorem 1 and Corollary 2 establish the expected convergence performance over many runs of the RSG method, we are also interested in the large-deviation properties for a single run of this method. In particular, we are interested in establishing its complexity for computing an $(\epsilon,\Lambda)$-solution of problem (1.1), i.e., a point $\bar{x}$ satisfying $\mathop{\rm Prob}\{\|\nabla f(\bar{x})\|^{2}\leq\epsilon\}\geq 1-\Lambda$ for some $\epsilon>0$ and $\Lambda\in(0,1)$. By using (2.14) and Markov’s inequality, we have

It then follows that the number of calls to ${\cal SFO}$ performed by the RSG method for finding an $(\epsilon,\Lambda)$-solution, after disregarding a few constant factors, can be bounded by

The above complexity bound is rather pessimistic in terms of its dependence on $\Lambda$. We will investigate one possible way to significantly improve it in next subsection.

2 A two-phase randomized stochastic gradient method

In this section, we describe a variant of the RSG method which can considerably improve the complexity bound in (2.20). This procedure consists of two phases: an optimization phase used to generate a list of candidate solutions via a few independent runs of the RSG method and a post-optimization phase in which a solution is selected from this candidate list.

Input: Initial point $x_{1}$, number of runs $S$, iteration limit $N$, and sample size $T$.

Call the RSG method with input $x_{1}$, iteration limit $N$, stepsizes $\{\gamma_{k}\}$ in (2.13) and probability mass function $P_{R}$ in (2.3). Let $\bar{x}_{s}$ be the output of this procedure.

Choose a solution $\bar{x}^{*}$ from the candidate list $\{\bar{x}_{1},\ldots,\bar{x}_{S}\}$ such that

where $G(x,\xi_{k})$, $k=1,\ldots,T$, are the stochastic gradients returned by the ${\cal SFO}$.

Observe that in (2.21), we define the best solution $\bar{x}^{*}$ as the one with the smallest value of $\|g(\bar{x}_{s})\|$, $s=1,\ldots,S$. Alternatively, one can choose $\bar{x}^{*}$ from $\{\bar{x}_{1},\ldots,\bar{x}_{S}\}$ such that

It should be noted that the $2$-RSG method is different from a two-phase procedure for convex stochastic programming by Nesterov and Vial , where the average of $\bar{x}_{1},\ldots,\bar{x}_{S}$ is chosen as the output solution.

In the $2$-RSG method described above, the number of calls to the ${\cal SFO}$ are given by $S\times N$ and $S\times T$, respectively, for the optimization phase and post-optimization phase. Also note that we can possibly recycle the same sequence $\{\xi_{k}\}$ across all gradient estimations in the post-optimization phase of $2$-RSG method. We will provide in Theorem 4 below certain bounds on $S$, $N$ and $T$, to compute an $(\epsilon,\Lambda)$-solution of problem (1.1).

We need the following results regarding the large deviations of vector valued martingales (see, e.g., Theorem 2.1 of ).

We are now ready to describe the main convergence properties of the $2$-RSG method. More specifically, Theorem 4.a) below shows the convergence rate of this algorithm for a given set of parameters $(S,N,T)$, while Theorem 4.b) establishes the complexity of the $2$-RSG method for computing an $(\epsilon,\Lambda)$-solution of problem (1.1).

Under Assumption A1, the following statements hold for the $2$-RSG method applied to problem (1.1).

Let ${\cal B}_{N}$ be defined in (2.14). We have

Let $\epsilon>0$ and $\Lambda\in(0,1)$ be given. If the parameters $(S,N,T)$ are set to

then the $2$-RSG method can compute an $(\epsilon,\Lambda)$-solution of problem (1.1) after taking at most

calls to the stochastic first-order oracle.

Proof. We first show part a). Observe that by the definition of $\bar{x}^{*}$ in (2.21), we have

We now provide certain probabilistic upper bounds to the three terms in the right hand side of the above inequality. Firstly, using the fact that $\bar{x}_{s}$, $1\leq s\leq S$, are independent and relation (2.19) (with $\lambda=2$), we have

Moreover, denoting $\delta_{s,k}=G(\bar{x}_{s},\xi_{k})-\nabla f(\bar{x}_{s})$, $k=1,\ldots,T$, we have $g(\bar{x}_{s})-\nabla f(\bar{x}_{s})=\sum_{k=1}^{T}\delta_{s,k}/T$. Using this observation, Assumption A1 and Lemma 3.a), we conclude that, for any $s=1,\ldots,S$,

The result then follows by combining relations (2.28), (2.29), (2.30) and (2.31).

We now show that part b) holds. Since the $2$-RSG method needs to call the RSG method $S$ times with iteration limit $N(\epsilon)$ in the optimization phase, and estimate the gradients $g(\bar{x}_{s})$, $s=1,\ldots,S$ with sample size $T(\epsilon)$ in the post-optimization phase, the total number of calls to the stochastic first-order oracle is bounded by $S[N(\epsilon)+T(\epsilon)]$. It remains to show that $\bar{x}^{*}$ is an $(\epsilon,\Lambda)$-solution of problem (1.1). Noting that by the definitions of ${\cal B}_{N}$ and $N(\epsilon)$, respectively, in (2.14) and (2.25), we have

Using the above observation, (2.26) and setting $\lambda=[2(S+1)]/\Lambda$ in (2.23), we have

which, together with relations (2.23) and (2.24), and the selection of $\lambda$, then imply that

It is interesting to compare the complexity bound in (2.27) with the one in (2.20). In view of (2.24), (2.25) and (2.26), the complexity bound in (2.27), after disregarding a few constant factors, is equivalent to

The above bound can be considerably smaller than the one in (2.20) up to a factor of $1/\left[\Lambda^{2}\log(1/\Lambda)\right],$ when the second terms are the dominating ones in both bounds.

The following result shows that the bound (2.27) obtained in Theorem 4 can be further improved under certain light-tail assumption of ${\cal SFO}$.

Under Assumptions A1 and A2, the following statements hold for the $2$-RSG method applied to problem (1.1).

Let ${\cal B}_{N}$ is defined in (2.14). We have, $\forall\,\lambda>0$,

Let $\epsilon>0$ and $\Lambda\in(0,1)$ be given. If $S$ and $N$ are set to $S(\Lambda)$ and $N(\epsilon)$ as in (2.24) and (2.25), respectively, and the sample size $T$ is set to

then the $2$-RSG method can compute an $(\epsilon,\Lambda)$-solution of problem (1.1) in at most

calls to the stochastic first-order oracle.

Proof. We provide the proof of part a) only, since part b) follows immediately from part a) and an argument similar to the one used in the proof of Theorem 4.b). Denoting $\delta_{s,k}=G(\bar{x}_{s},\xi_{k})-\nabla f(\bar{x}_{s})$, $k=1,\ldots,T$, we have $g(\bar{x}_{s})-\nabla f(\bar{x}_{s})=\sum_{k=1}^{T}\delta_{s,k}/T$. Using this observation, Assumption A2 and Lemma 3.b), we conclude that, for any $s=1,\ldots,S$ and $\lambda>0$,

The result in part a) then follows by combining relations (2.28), (2.29), (2.36) and (2.37).

In view of (2.24), (2.25) and (2.34), the bound in (2.35), after disregarding a few constant factors, is equivalent to

Clearly, the third term of the above bound is significantly smaller than the corresponding one in (2.32) by a factor of $1/\Lambda$.

Stochastic zeroth-order methods

Our problem of interest in this section is problem (1.1) with $f$ given in (1.4), i.e.,

Throughout this section, we assume that $f$ is represented by a stochastic zeroth-order oracle ($\cal SZO$). More specifically, at the $k$-th iteration, $x_{k}$ and $\xi_{k}$ being the input, the $\cal SZO$ outputs the quantity $F(x_{k},\xi_{k})$ such that the following assumption holds:

The following result due to Nesterov describes some properties of $f_{\mu}(\cdot)$.

The following statements hold for any $f\in{\cal C}^{1,1}_{L}$.

is Lipschitz continuous with constant $L_{\mu}$ such that $L_{\mu}\leq L$;

we conclude from (3.5) that $|f_{\mu}^{*}-f^{*}|\leq\mu^{2}Ln/2$ and hence that

Below we modify the RSG method in subsection (2.1) to use stochastic zeroth-order rather than first-order information for solving problem (3.1).

A randomized stochastic gradient free (RSGF) method

Input: Initial point $x_{1}$, iteration limit $N$, stepsizes $\{\gamma_{k}\}_{k\geq 1}$, probability mass function $P_{R}(\cdot)$ supported on $\{1,\ldots,N\}$.

Step . Let $R$ be a random variable with probability mass function $P_{R}$.

Step $k=1,\ldots,R$. Generate $u_{k}$ by Gaussian random vector generator and call the stochastic zeroth-order oracle for computing $G_{\mu}(x_{k},\xi_{k},u_{k})$ given by

Note that the esimator $G_{\mu}(x_{k},\xi_{k},u_{k})$ of $\nabla f_{\mu}(x_{k})$ in (3.12) was suggested by Nesterov in . Indeed, by (3.4) and Assumption A3, we have

By applying the approximation results in Theorem 6 to the functions $F(\cdot,\xi_{k})$, $k=1,\ldots,N$, and using a slightly different convergence analysis than the one in Theorem 1, we are able to obtain much refined convergence results for the above RSGF method.

Suppose that the stepsizes $\{\gamma_{k}\}$ and the probability mass function $P_{R}(\cdot)$ in the RSGF method are chosen such that $\gamma_{k}<1/[2(n+4)L]$ and

where the expectation is taken with respect to $R$, $\xi_{[N]}$ and $u_{[N]}$, and $D_{f}$ is defined in(2.5);

if, in addition, problem (3.1) is convex with an optimal solution $x^{*}$, then, for any $N\geq 1$,

where the expectation is taken with respect to $R$, $\xi_{[N]}$ and $u_{[N]}$, and $D_{X}$ is defined in (2.7).

Summing up these inequalities, re-arranging the terms and noting that $f^{*}_{\mu}\leq f_{\mu}(x_{N+1})$, we obtain

where the second inequality follows from Assumption A1. Taking expectations with respect to $\zeta_{[N]}$ on both sides of (3.19) and using the above two observations, we obtain

The above conclusion together with (3.8) and (3.11) then imply that

By re-arranging the terms and simplifying the constants, we have

Dividing both sides of the above inequality by $\sum_{k=1}^{N}\left[\gamma_{k}-2L(n+4)\gamma_{k}^{2}\right]$ and noting that

We now show part b). Denote $\omega_{k}\equiv\|x_{k}-x^{*}\|$. First observe that, for any $k=1,\ldots,N$,

where the second inequality follows from (2.12) and the convexity of $f_{\mu}$, and the last inequality follows from (3.5). Re-arranging the terms in the above inequality, using the facts that $\omega_{N+1}^{2}\geq 0$ and $f(x_{k})\geq f^{*}$, and simplifying the constants, we have

The rest of proof is similar to part a) and hence the details are skipped.

Similarly to the RSG method, we can specialize the convergence results in Theorem 7 for the RSGF method with a constant stepsize policy.

Suppose that the stepsizes $\{\gamma_{k}\}$ are set to

where $D_{f}$ and $D_{X}$ are defined in (2.5) and (2.7), respectively. Then, under Assumptions A1 and A3, we have

If, in addition, problem (3.1) is convex with an optimal solution $x^{*}$ and $\mu$ is chosen such that

Proof. We prove (3.26) only since relation (3.27) can be shown by using similar arguments. First note that by (3.24), we have

Therefore, using the above inequalities and (3.16), we obtain

which, in view of (3.25), then implies that

Similarly to the RSG method, we can establish the complexity of the RSGF method for finding an $(\epsilon,\Lambda)$-solution of problem (3.1) for some $\epsilon>0$ and $\Lambda\in(0,1)$. More specifically, by using (3.26) and Markov’s inequality, we have

which implies that the total number of calls to the ${\cal SZO}$ performed by the RSGF method for finding an $(\epsilon,\Lambda)$-solution of (3.1) can be bounded by

We will investigate a possible approach to improve the above complexity bound in next subsection.

2 A two-phase randomized stochastic gradient free method

In this section, we modify the 2-RSG method to improve the complexity bound in (3.33) for finding an $(\epsilon,\Lambda)$-solution of problem (3.1).

Input: Initial point $x_{1}$, number of runs $S$, iteration limit $N$, and sample size $T$.

Call the RSGF method with input $x_{1}$, iteration limit $N$, stepsizes $\{\gamma_{k}\}$ in (3.24), probability mass function $P_{R}$ in (3.15), and the smoothing parameter $\mu$ satisfying (3.25). Let $\bar{x}_{s}$ be the output of this procedure.

Choose a solution $\bar{x}^{*}$ from the candidate list $\{\bar{x}_{1},\ldots,\bar{x}_{S}\}$ such that

where $G_{\mu}(x,\xi,u)$ is defined in (3.12).

The main convergence properties of the $2$-RSGF method are summarized in Theorem 9. More specifically, Theorem 9.a) establishes the rate of convergence of the $2$-RSGF method with a given set of parameters $(S,N,T)$, while Theorem 9.b) shows the complexity of this method for finding an $(\epsilon,\Lambda)$-solution of problem (3.1).

Under Assumptions A1 and A3, the following statements hold for the $2$-RSGF method applied to problem (3.1).

Let $\bar{{\cal B}}_{N}$ be defined in (3.26). We have

Let $\epsilon>0$ and $\Lambda\in(0,1)$ be given. If $S$ is set to $S(\Lambda)$ as in (2.24), and the iteration limit $N$ and sample size $T$, respectively, are set to

then the $2$-RSGF method can compute an $(\epsilon,\Lambda)$-solution of problem (3.1) after taking at most

Proof. First, observe that by (3.6), (3.25) and (3.26), we have

Using this observation and the definition of $\bar{x}^{*}$ in (3.34), we obtain

where the last inequality also follows from (3.39). We now provide certain probabilistic bounds on the individual terms in the right hand side of the above inequality. Using (3.32) (with $\lambda=2$), we obtain

Moreover, denote $\Delta_{s,k}=G_{\mu}(\bar{x}_{s},\xi_{k},u_{k})-\nabla f_{\mu}(\bar{x}_{s})$, $k=1,\ldots,T$. Note that, similar to (3.21), we have

It then follows from the previous inequality, (3.25) and (3.26) that

Noting that $g_{\mu}(\bar{x}_{s})-\nabla f_{\mu}(\bar{x}_{s})=\sum_{k=1}^{T}\Delta_{s,k}/T$, we conclude from (3.42), Assumption A1 and Lemma 3.a) that, for any $s=1,\ldots,S$,

The result then follows by combining relations (3.40), (3.41),(3.42), (3.43) and (3.44).

We now show part b) holds. Clearly, the total number of calls to $\cal SZO$ in the $2$-RSGF method is bounded by $2S[\hat{N}(\epsilon)+\hat{T}(\epsilon)]$. It then suffices to show that $\bar{x}^{*}$ is an $(\epsilon,\Lambda)$-solution of problem (3.1). Noting that by the definitions of $\bar{{\cal B}}(N)$ and $\hat{N}(\epsilon)$, respectively, in (3.26) and (3.36), we have

Moreover, by setting $\lambda=[2(S+1)]/\Lambda$ and using (3.36) and (3.37), we obtain

Using these two observations and relation (3.35) with $\lambda=[2(S+1)]/\Lambda$, we conclude that

Observe that in the view of (2.24), (3.36) and (3.37), the total number of calls to $\cal SZO$ performed by the $2$-RSGF method can be bounded by

The above bound is considerably smaller than the one in (3.33), up to a factor of ${\cal O}\left(1/[\Lambda^{2}\log(1/\Lambda)]\right),$ when the second terms are the dominating ones in both bounds.

Concluding remarks

In this paper, we present a class of new SA methods for solving the classical unconstrained NLP problem with noisy first-order information. We establish a few new complexity results regarding the computation of an $\epsilon$-solution for solving this class of problems and show that they are nearly optimal whenever the problem is convex. Moreover, we introduce a post-optimization phase in order to improve the large-deviation properties of the RSG method. These procedures, along with their complexity results, are then specialized for simulation-based optimization problems when only stochastic zeroth-order information is available. In addition, we show that the complexity for gradient-free methods for smooth convex SP can have a much weaker dependence on the dimension $n$ than that for more general nonsmooth convex SP.

References