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

Saeed GhadimiGuanghui Lan

article2013SIAM Journal on Optimization1,965 citations

Develops randomized stochastic gradient and zeroth-order methods that establish theoretical complexity guarantees for finding approximate stationary points in nonconvex stochastic optimization.

Listen

Many critical applications in machine learning, industrial operations, and complex simulations require optimizing systems subject to noise and uncertainty. While traditional stochastic approximation methods solve convex problems efficiently, real-world problems often exhibit nonconvexity—such as complex loss functions or black-box simulations where true gradients are noisy or entirely unavailable. Historical optimization algorithms lack theoretical convergence guarantees and reliable performance bounds when applied to these general nonconvex stochastic settings.

The article establishes theoretical convergence complexity bounds and introduces practical, robust algorithms for solving smooth, potentially nonconvex stochastic optimization problems using either noisy gradient information (first-order) or noisy function values alone (zeroth-order).

The authors develop the Randomized Stochastic Gradient (RSG) method, which selects an output solution randomly from its iteration path rather than relying on iterate averaging. To enhance reliability and minimize variance across single runs, they design a two-phase framework (2-RSG) that evaluates a short candidate list of solutions generated across multiple independent runs. Furthermore, by incorporating Gaussian smoothing techniques, they extend both algorithms to derivative-free settings, creating the Randomized Stochastic Gradient Free (RSGF) and two-phase RSGF methods for simulation-based problems. The authors evaluate their methods through theoretical complexity proofs and numerical experiments across three domains: a convex least-squares problem, a nonconvex support vector machine classification task, and a simulation-based inventory management problem.

The article yields several key findings:

Theoretical Convergence: The RSG method achieves a guaranteed stationary point convergence rate of order 1/ε² for general nonconvex stochastic problems, while simultaneously maintaining a nearly optimal convergence rate for convex instances.
Enhanced Reliability via Two-Phase Sampling: A single run of the baseline RSG algorithm exhibits significant outcome variability. Adding a post-optimization evaluation phase in the 2-RSG method drastically reduces error probabilities and cuts sample complexity bounds by factors proportional to the failure tolerance.
Derivative-Free Efficiency: The RSGF algorithm achieves an iteration complexity of order n/ε² for stochastic zeroth-order problems. For smooth convex stochastic optimization, this improves the dimensional dependence on n compared to previous general nonsmooth methods.
Empirical Superiority: In numerical tests, the two-phase variants consistently matched or outperformed standard mirror descent stochastic approximation. On the nonconvex support vector machine problem, the two-phase approach achieved misclassification error rates substantially lower than iterate-averaging methods (for example, reducing error to roughly 8–18% compared to over 20–46% for traditional iterate averaging at higher sample budgets).

These findings provide strong mathematical justification and practical algorithms for optimizing complex, nonconvex operations under severe uncertainty. Organizations relying on black-box simulations or machine learning models can avoid the heuristic trial-and-error approach common in nonconvex tuning. By using two-phase post-optimization validation, decision-makers can achieve high-confidence solutions with predictable computational budgets, lowering both optimization risk and computing costs.

Practitioners should implement the two-phase randomized frameworks (2-RSG or 2-RSGF) rather than single-run randomized search or traditional iterate averaging when dealing with nonconvex objectives. When selecting algorithmic parameters, practitioners can estimate the Lipschitz smoothness constant using a small preliminary sample of trial points, as the method remains robust even if smoothness is overestimated by an order of magnitude. For derivative-free simulation problems, teams should adopt Gaussian smoothing with the specified stepsize rules to balance bias and variance efficiently.

The theoretical guarantees assume smooth objective functions with bounded gradient variance and focus on unconstrained optimization or stationary point discovery rather than global optimality. While confidence in the mathematical bounds and empirical performance is high, practitioners should note that finding approximate stationary points in nonconvex landscapes does not entirely rule out local suboptimality, and applying the method to constrained problems may require further extensions.

University of Florida nonconvex optimization stochastic nonconvex stochastic programming stochastic zeroth-order methods stochastic gradient-free method

arXiv: 1309.5549

Paper: A Stochastic Approximation Method, Herbert Robbins et al. (1951). Introduces the seminal stochastic approximation framework that serves as the foundation for the randomized stochastic gradient methods analyzed in the paper.
Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). Establishes modern stochastic subgradient methods and convergence rates for stochastic optimization problems that precede nonconvex extensions.
Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). Provides the foundational projection and regret analysis principles for online and stochastic gradient descent across constrained domains.

Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). Surveys large-scale stochastic optimization, incorporating and building upon the complexity results and stationarity concepts established for nonconvex stochastic programming.
Paper: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson et al. (2013). Develops stochastic variance reduction (SVRG) to accelerate stochastic gradient descent beyond standard sublinear convergence rates.
Paper: SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives, Aaron Defazio et al. (2014). Extends variance reduction techniques to handle non-strongly convex and composite stochastic optimization objectives.
Paper: An overview of gradient descent optimization algorithms, Sebastian Ruder (2016). Provides an applied overview of first-order stochastic optimization variants designed to tackle practical nonconvex machine learning landscapes.
Paper: On the Convergence of Adam and Beyond, Sashank J. Reddi et al. (2018). Analyzes the convergence properties of adaptive stochastic gradient algorithms in both convex and nonconvex optimization settings.

Cover for Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming

Abstract

In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this method possesses a nearly optimal rate of convergence if the problem is convex. We discuss a variant of the algorithm which consists of applying a post-optimization phase to evaluate a short list of solutions generated by several independent runs of the RSG method, and show that such modification allows to improve significantly the large-deviation properties of the algorithm. These methods are then specialized for solving a class of simulation-based optimization problems in which only stochastic zeroth-order information is available.

Topics

nonconvex optimization stochastic stochastic approximation stochastic programming programming languages

Keywords

nonconvex stochastic programming stochastic zeroth-order methods stochastic gradient-free method stochastic first-order oracle stochastic approximation method nonconvex support vector machine simulation-based optimization composite optimization

1 Introduction
1.1 Notation and terminology
2 Stochastic first-order methods
2.1 The randomized stochastic gradient method
2.2 A two-phase randomized stochastic gradient method
3 Stochastic zeroth-order methods
3.1 The randomized stochastic gradient free method
3.2 A two-phase randomized stochastic gradient free method
4 Concluding remarks
References

Knowls

Knowl 1 — Randomized Stochastic Gradient Method
algorithm
The Randomized Stochastic Gradient (RSG) algorithm solves unconstrained nonlinear stochastic programming problems of the form $\min_{x \in \mathbb{R}^n} f(x)$ , where $f: \mathbb{R}^n \to \mathbb{R}$ is continuously differentiable with $L$ -Lipschitz continuous gradient ( $\|\nabla f(y) - \nabla f(x)\| \le L \|y - x\|$ ) and bounded below by $f^* > -\infty$ . Access to $f$ is provided via a Stochastic First-Order Oracle (SFO) returning unbiased stochastic gradients $G(x_k, \xi_k)$ with bounded variance $\mathbb{E}[\|G(x_k, \xi_k) - \nabla f(x_k)\|^2] \le \sigma^2$ .
Input: Initial point $x_1 \in \mathbb{R}^n$ , iteration limit $N \ge 1$ , stepsizes $\{\gamma_k\}_{k=1}^N$ satisfying $\gamma_k < 2/L$ , and probability mass function $P_R$ supported on $\{1, \dots, N\}$ .
Output: Solution point $x_R \in \mathbb{R}^n$ .
Step 0. Draw integer iteration index $R \in \{1, \dots, N\}$ according to probability mass function:
         $P_R(k) := \text{Prob}\{R = k\} = \frac{2\gamma_k - L\gamma_k^2}{\sum_{i=1}^N (2\gamma_i - L\gamma_i^2)}, \quad k = 1, \dots, N$ .
Step 1. For $k = 1, \dots, R$ :
            Call SFO to compute $G(x_k, \xi_k)$ .
            Update $x_{k+1} = x_k - \gamma_k G(x_k, \xi_k)$ .
Step 2. Return $x_R$ .
Equivalently, the algorithm can be run for $N$ iterations and the output point $x_R$ sampled post-hoc from the trajectory $\{x_1, \dots, x_N\}$ according to the probability distribution $P_R$ .
Knowl 2 — Convergence Rate and Complexity of the RSG Method
theoretical result
Let $f: \mathbb{R}^n \to \mathbb{R}$ be $L$ -smooth ( $\|\nabla f(y) - \nabla f(x)\| \le L \|y - x\|$ ) and bounded below by $f^*$ . Let the stochastic gradient oracle $G(x, \xi)$ satisfy $\mathbb{E}[G(x, \xi)] = \nabla f(x)$ and $\mathbb{E}[\|G(x, \xi) - \nabla f(x)\|^2] \le \sigma^2$ . Let $D_f := \sqrt{2(f(x_1) - f^*)/L}$ .

If the stepsizes satisfy $\gamma_k < 2/L$ and the randomized termination index $R \in \{1, \dots, N\}$ is chosen with probability mass function $P_R(k) = \frac{2\gamma_k - L\gamma_k^2}{\sum_{i=1}^N (2\gamma_i - L\gamma_i^2)}$ , then for any $N \ge 1$ :

$\frac{1}{L}\mathbb{E}[\|\nabla f(x_R)\|^2] \le \frac{D_f^2 + \sigma^2 \sum_{k=1}^N \gamma_k^2}{\sum_{k=1}^N (2\gamma_k - L\gamma_k^2)},$

where the expectation is taken with respect to $R$ and the noise sequence $\xi_{[N]} = (\xi_1, \dots, \xi_N)$ .

Under the constant stepsize policy

$\gamma_k = \min\left\{\frac{1}{L}, \frac{\tilde{D}}{\sigma \sqrt{N}}\right\}, \quad k = 1, \dots, N$

for a chosen parameter $\tilde{D} > 0$ , the expected squared gradient norm satisfies:

$\frac{1}{L}\mathbb{E}[\|\nabla f(x_R)\|^2] \le \frac{L D_f^2}{N} + \left(\tilde{D} + \frac{D_f^2}{\tilde{D}}\right) \frac{\sigma}{\sqrt{N}}.$

Setting $\tilde{D} = D_f$ yields an iteration complexity of $\mathcal{O}(1/\epsilon^2)$ oracle calls to obtain $\mathbb{E}[\|\nabla f(x_R)\|^2] \le \epsilon$ .

If, in addition, $f$ is convex with an optimal solution $x^*$ and distance constant $D_X := \|x_1 - x^*\|$ , then under the same stepsize policy:

$\mathbb{E}[f(x_R) - f^*] \le \frac{L D_X^2}{N} + \left(\tilde{D} + \frac{D_X^2}{\tilde{D}}\right) \frac{\sigma}{\sqrt{N}},$

which guarantees $\mathbb{E}[f(x_R) - f^*] \le \epsilon$ within $\mathcal{O}(1/\epsilon^2)$ iterations.
Knowl 3 — Two-Phase Randomized Stochastic Gradient Method
algorithm
The Two-Phase Randomized Stochastic Gradient (2-RSG) method improves the large-deviation properties of the RSG method for computing an $(\epsilon, \Lambda)$ -solution to $\min_{x \in \mathbb{R}^n} f(x)$ , defined as a point $\bar{x}^*$ such that $\text{Prob}\{\|\nabla f(\bar{x}^*)\|^2 \le \epsilon\} \ge 1 - \Lambda$ for given target accuracy $\epsilon > 0$ and confidence level $1 - \Lambda \in (0, 1)$ .
Input: Initial point $x_1 \in \mathbb{R}^n$ , number of independent runs $S \ge 1$ , iteration limit per run $N \ge 1$ , and post-optimization sample size $T \ge 1$ .
Output: Selected solution $\bar{x}^* \in \mathbb{R}^n$ .
Step 1. [Optimization Phase]
        For $s = 1, \dots, S$ :
            Execute the RSG algorithm with initial point $x_1$ , iteration limit $N$ , stepsizes $\gamma_k = \min\{1/L, \tilde{D}/(\sigma\sqrt{N})\}$ , and probability mass function $P_R(k) = 1/N$ .
            Let $\bar{x}_s$ denote the output of run $s$ .
Step 2. [Post-Optimization Phase]
        For each candidate solution $\bar{x}_s \in \{\bar{x}_1, \dots, \bar{x}_S\}$ :
            Sample $T$ independent realizations of the noise vector $\{\xi_{s,1}, \dots, \xi_{s,T}\}$ .
            Compute the sample average stochastic gradient:
             $g(\bar{x}_s) = \frac{1}{T} \sum_{k=1}^T G(\bar{x}_s, \xi_{s,k})$ .
Step 3. Select $\bar{x}^* \in \{\bar{x}_1, \dots, \bar{x}_S\}$ with the minimum estimated gradient norm:
         $\|g(\bar{x}^*)\| = \min_{s=1, \dots, S} \|g(\bar{x}_s)\|$ .
Step 4. Return $\bar{x}^*$ .
For convex problems, Step 3 can alternatively select $\bar{x}^*$ by minimizing the sample average function value $\tilde{f}(\bar{x}_s) = \frac{1}{T}\sum_{k=1}^T F(\bar{x}_s, \xi_{s,k})$ .
Knowl 4 — High-Probability Oracle Complexity of the 2-RSG Method
theoretical result
Let $f: \mathbb{R}^n \to \mathbb{R}$ have $L$ -Lipschitz continuous gradient and lower bound $f^*$ . Let the stochastic first-order oracle satisfy $\mathbb{E}[G(x, \xi)] = \nabla f(x)$ and $\mathbb{E}[\|G(x, \xi) - \nabla f(x)\|^2] \le \sigma^2$ . Let $D_f := \sqrt{2(f(x_1) - f^*)/L}$ , $\epsilon > 0$ , and $\Lambda \in (0, 1)$ .

When the 2-RSG method parameters are configured as:

$S = S(\Lambda) := \lceil \log_2(2/\Lambda) \rceil,$

$N = N(\epsilon) := \left\lceil \max\left\{ \frac{32 L^2 D_f^2}{\epsilon}, \left[\frac{32 L}{\epsilon} \left(\tilde{D} + \frac{D_f^2}{\tilde{D}}\right) \sigma\right]^2 \right\} \right\rceil,$

$T = T(\epsilon, \Lambda) := \left\lceil \frac{24(S + 1)\sigma^2}{\Lambda \epsilon} \right\rceil,$

the resulting output $\bar{x}^*$ satisfies $\text{Prob}\{\|\nabla f(\bar{x}^*)\|^2 \le \epsilon\} \ge 1 - \Lambda$ , and the total number of calls to the stochastic first-order oracle is bounded by:

$S(\Lambda)[N(\epsilon) + T(\epsilon, \Lambda)] = \mathcal{O}\left( \frac{L^2 D_f^2 \log(1/\Lambda)}{\epsilon} + \frac{L^2 \sigma^2 \log(1/\Lambda)}{\epsilon^2} + \frac{\sigma^2 \log^2(1/\Lambda)}{\Lambda \epsilon} \right).$

If the noise additionally satisfies the light-tail condition $\mathbb{E}[\exp\{\|G(x, \xi) - \nabla f(x)\|^2 / \sigma^2\}] \le \exp\{1\}$ , setting the post-optimization sample size to

$T'(\epsilon, \Lambda) := \left\lceil \frac{24\sigma^2}{\epsilon} \left[ 1 + \left( 3 \ln \frac{2(S + 1)}{\Lambda} \right)^{1/2} \right]^2 \right\rceil$

reduces the total oracle calls to:

$S(\Lambda)[N(\epsilon) + T'(\epsilon, \Lambda)] = \mathcal{O}\left( \frac{L^2 D_f^2 \log(1/\Lambda)}{\epsilon} + \frac{L^2 \sigma^2 \log(1/\Lambda)}{\epsilon^2} + \frac{\sigma^2 \log^2(1/\Lambda)}{\epsilon} \right).$
Knowl 5 — Randomized Stochastic Gradient Free Method
algorithm
The Randomized Stochastic Gradient Free (RSGF) method optimizes stochastic objective functions $f(x) := \mathbb{E}_\xi[F(x, \xi)]$ when only noisy zeroth-order function values $F(x, \xi)$ are accessible via a Stochastic Zeroth-Order Oracle (SZO), where $\mathbb{E}[F(x, \xi)] = f(x)$ and $F(\cdot, \xi) \in C_L^{1,1}(\mathbb{R}^n)$ almost surely.
Input: Initial point $x_1 \in \mathbb{R}^n$ , iteration limit $N \ge 1$ , stepsizes $\{\gamma_k\}_{k=1}^N$ satisfying $\gamma_k < \frac{1}{2(n+4)L}$ , smoothing parameter $\mu > 0$ , and probability mass function $P_R$ supported on $\{1, \dots, N\}$ .
Output: Solution point $x_R \in \mathbb{R}^n$ .
Step 0. Draw integer index $R \in \{1, \dots, N\}$ according to probability mass function:
         $P_R(k) := \text{Prob}\{R = k\} = \frac{\gamma_k - 2L(n+4)\gamma_k^2}{\sum_{i=1}^N [\gamma_i - 2L(n+4)\gamma_i^2]}, \quad k = 1, \dots, N$ .
Step 1. For $k = 1, \dots, R$ :
            Generate standard Gaussian random vector $u_k \sim \mathcal{N}(0, I_n)$ .
            Query the SZO at $x_k + \mu u_k$ and $x_k$ using the same noise realization $\xi_k$ .
            Compute the stochastic gradient estimate:
             $G_\mu(x_k, \xi_k, u_k) = \frac{F(x_k + \mu u_k, \xi_k) - F(x_k, \xi_k)}{\mu} u_k$ .
            Update $x_{k+1} = x_k - \gamma_k G_\mu(x_k, \xi_k, u_k)$ .
Step 2. Return $x_R$ .
Knowl 6 — Convergence Rate and Complexity of the RSGF Method
theoretical result
Let $f(x) := \mathbb{E}_\xi[F(x, \xi)]$ with $f^* := \inf_{x \in \mathbb{R}^n} f(x) > -\infty$ , where $F(\cdot, \xi)$ is $L$ -smooth almost surely. Let $\mathbb{E}[\|\nabla F(x, \xi) - \nabla f(x)\|^2] \le \sigma^2$ , and define $D_f := \sqrt{2(f(x_1) - f^*)/L}$ .

If the smoothing parameter $\mu$ and stepsizes $\{\gamma_k\}$ in the RSGF method are chosen as:

$\mu \le \frac{D_f}{(n+4)\sqrt{2N}}, \quad \gamma_k = \frac{1}{\sqrt{n+4}} \min\left\{\frac{1}{4L\sqrt{n+4}}, \frac{\tilde{D}}{\sigma \sqrt{N}}\right\}, \quad k = 1, \dots, N,$

for any parameter $\tilde{D} > 0$ , and $P_R(k) \propto \gamma_k - 2L(n+4)\gamma_k^2$ , then:

$\frac{1}{L}\mathbb{E}[\|\nabla f(x_R)\|^2] \le \frac{12(n+4)LD_f^2}{N} + \frac{4\sigma\sqrt{n+4}}{\sqrt{N}}\left(\tilde{D} + \frac{D_f^2}{\tilde{D}}\right).$

Consequently, finding a point $x_R$ such that $\mathbb{E}[\|\nabla f(x_R)\|^2] \le \epsilon$ requires at most $\mathcal{O}(n/\epsilon^2)$ calls to the stochastic zeroth-order oracle. For deterministic zeroth-order optimization ( $\sigma = 0$ ), the complexity is $\mathcal{O}(n/\epsilon)$ .

If, in addition, $f$ is convex with optimal solution $x^*$ and $D_X := \|x_1 - x^*\|$ , setting $\mu \le D_X / \sqrt{n+4}$ yields:

$\mathbb{E}[f(x_R) - f^*] \le \frac{5L(n+4)D_X^2}{N} + \frac{2\sigma\sqrt{n+4}}{\sqrt{N}}\left(\tilde{D} + \frac{D_X^2}{\tilde{D}}\right),$

which guarantees $\mathbb{E}[f(x_R) - f^*] \le \epsilon$ in $\mathcal{O}(n/\epsilon^2)$ oracle calls.
Knowl 7 — Two-Phase Randomized Stochastic Gradient Free Method and Complexity
theoretical result
The Two-Phase Randomized Stochastic Gradient Free (2-RSGF) method computes an $(\epsilon, \Lambda)$ -solution for zeroth-order stochastic optimization $\min_{x \in \mathbb{R}^n} f(x) := \mathbb{E}_\xi[F(x, \xi)]$ using only noisy function queries.

In the optimization phase, $S$ independent runs of the RSGF method are executed with iteration limit $N$ and smoothing parameter $\mu \le D_f / ((n+4)\sqrt{2N})$ to produce candidate solutions $\{\bar{x}_1, \dots, \bar{x}_S\}$ . In the post-optimization phase, each candidate's gradient is estimated by:

$g_\mu(\bar{x}_s) = \frac{1}{T} \sum_{k=1}^T \frac{F(\bar{x}_s + \mu u_k, \xi_k) - F(\bar{x}_s, \xi_k)}{\mu} u_k,$

where $u_k \sim \mathcal{N}(0, I_n)$ , and the algorithm outputs $\bar{x}^* = \arg\min_{s=1,\dots,S} \|g_\mu(\bar{x}_s)\|$ .

Setting the hyperparameters to:

$S = S(\Lambda) := \lceil \log_2(2/\Lambda) \rceil,$

$\hat{N}(\epsilon) := \left\lceil \max\left\{ \frac{12(n+4)(6LD_f)^2}{\epsilon}, \left[\frac{72L\sqrt{n+4}}{\epsilon}\left(\tilde{D} + \frac{D_f^2}{\tilde{D}}\right)\sigma\right]^2 \right\} \right\rceil,$

$\hat{T}(\epsilon, \Lambda) := \left\lceil \frac{24(n+4)(S+1)}{\Lambda} \max\left\{1, \frac{6\sigma^2}{\epsilon}\right\} \right\rceil,$

guarantees $\text{Prob}\{\|\nabla f(\bar{x}^*)\|^2 \le \epsilon\} \ge 1 - \Lambda$ . The total number of stochastic zeroth-order oracle calls is bounded by $2S(\Lambda)[\hat{N}(\epsilon) + \hat{T}(\epsilon, \Lambda)]$ , which is:

$\mathcal{O}\left( \frac{n L^2 D_f^2 \log(1/\Lambda)}{\epsilon} + n L^2 \left(\tilde{D} + \frac{D_f^2}{\tilde{D}}\right)^2 \frac{\sigma^2}{\epsilon^2} \log\frac{1}{\Lambda} + \frac{n \log^2(1/\Lambda)}{\Lambda}\left(1 + \frac{\sigma^2}{\epsilon}\right) \right).$
Knowl 8 — Gaussian Smoothing Gradient Approximations for Zeroth-Order Optimization
theoretical result
Let $f: \mathbb{R}^n \to \mathbb{R}$ be continuously differentiable with $L$ -Lipschitz continuous gradient ( $\|\nabla f(y) - \nabla f(x)\| \le L\|y - x\|$ ). For a smoothing parameter $\mu > 0$ and standard Gaussian random vector $u \sim \mathcal{N}(0, I_n)$ , the Gaussian smoothed approximation of $f$ is defined as:

$f_\mu(x) := \frac{1}{(2\pi)^{n/2}} \int_{\mathbb{R}^n} f(x + \mu u) e^{-\frac{1}{2}\|u\|^2} du = \mathbb{E}_u[f(x + \mu u)].$

The approximation $f_\mu$ and its gradient satisfy:
1. $f_\mu$ is continuously differentiable with Lipschitz constant $L_\mu \le L$ , and its gradient is:
$\nabla f_\mu(x) = \frac{1}{(2\pi)^{n/2}} \int_{\mathbb{R}^n} \frac{f(x + \mu u) - f(x)}{\mu} u e^{-\frac{1}{2}\|u\|^2} du = \mathbb{E}_u\left[\frac{f(x + \mu u) - f(x)}{\mu} u\right].$
1. The approximation errors are bounded by:
$|f_\mu(x) - f(x)| \le \frac{\mu^2}{2} L n,$

$\|\nabla f_\mu(x) - \nabla f(x)\| \le \frac{\mu}{2} L (n + 3)^{3/2}.$
1. The second moment of the zeroth-order finite difference estimator satisfies:
$\frac{1}{\mu^2} \mathbb{E}_u\left[\{f(x + \mu u) - f(x)\}^2 \|u\|^2\right] \le \frac{\mu^2}{2} L^2 (n+6)^3 + 2(n+4)\|\nabla f(x)\|^2.$
1. The squared norm of the true gradient is bounded by the smoothed gradient norm via:
$\|\nabla f(x)\|^2 \le 2 \|\nabla f_\mu(x)\|^2 + \frac{\mu^2}{2} L^2 (n+3)^3.$
Knowl 9 — Trajectory-Sampled Two-Phase Method (2-RSG-V)
model/method
The 2-RSG-V method is a variant of the Two-Phase Randomized Stochastic Gradient method designed to avoid running multiple independent optimization runs from scratch.

In the optimization phase, instead of executing the RSG algorithm $S$ independent times with a random termination index $R$ , the 2-RSG-V method executes a single continuous optimization trajectory of length $N_{total} = NS$ . From this generated trajectory $\{x_1, \dots, x_{N_{total}}\}$ , it draws $S$ candidate points $\{\bar{x}_1, \dots, \bar{x}_S\}$ by sampling with replacement according to the probability mass function:

$P_R(k) = \frac{2\gamma_k - L\gamma_k^2}{\sum_{i=1}^{N_{total}} (2\gamma_i - L\gamma_i^2)}, \quad k = 1, \dots, N_{total}.$

In the post-optimization phase, identical to 2-RSG, an independent i.i.d. sample of size $T$ is used to estimate the gradient $g(\bar{x}_s) = \frac{1}{T}\sum_{k=1}^T G(\bar{x}_s, \xi_k)$ for each candidate $s = 1, \dots, S$ , and the candidate $\bar{x}^*$ with the smallest estimated gradient norm $\|g(\bar{x}_s)\|$ is selected as the output.

Because all $NS$ iterations are performed sequentially along one trajectory, the later candidate points benefit from more gradient descent steps than candidates from $S$ separate runs of length $N$ , leading to superior empirical accuracy for the same total oracle budget.

Knowl 10 — Performance of Stochastic First-Order Methods on Nonconvex Support Vector Machines

empirical result

Stochastic first-order optimization methods were evaluated on a nonconvex support vector machine problem with a sigmoid loss function:

$\min_{x \in \mathbb{R}^n} f(x) := \mathbb{E}_{u, v}\left[1 - \tanh(v \langle x, u \rangle)\right] + \lambda \|x\|_2^2,$

where $u \in \{0, 1\}^n$ has $5\%$ non-zero entries, $v = \text{sign}(\langle \bar{x}, u \rangle) \in \{-1, 1\}$ , and $\lambda = 0.01$ . The compared algorithms include single-run RSG, 2-RSG (with $S = 5$ independent runs and post-optimization sample size $T = N/2$ ), 2-RSG-V (single trajectory of length $NS$ with $S = 5$ sampled candidate solutions), and Mirror Descent SA (MD-SA, which averages the trajectory), evaluated over 20 runs across dimensions $n \in \{100, 500, 1000\}$ and total optimization call budgets $NS \in \{1000, 5000, 25000\}$ .

$n$	$NS$	RSG	2-RSG	2-RSG-V	MD-SA
100	1000	0.0834 (9.73e-3)	0.0821 (3.77e-4)	0.0184 (5.06e-5)	0.0625 (8.75e-8)
	5000	0.0404 (8.04e-3)	0.0212 (1.29e-4)	0.0035 (3.33e-6)	0.0208 (2.93e-8)
	25000	0.0016 (4.58e-6)	0.0027 (1.04e-6)	0.0021 (2.15e-5)	0.0087 (9.14e-9)
500	1000	0.8165 (1.91e-1)	0.7423 (1.50e-2)	0.2769 (6.90e-3)	0.5837 (5.44e-9)
	5000	0.2865 (1.43e-1)	0.2630 (1.36e-2)	0.0510 (2.54e-3)	0.2137 (3.37e-8)
	25000	0.2741 (2.92e-1)	0.0549 (2.75e-3)	0.0068 (1.64e-4)	0.0525 (2.70e-8)
1000	1000	1.392 (9.49e-1)	1.428 (2.49e-2)	0.5557 (2.75e-2)	1.5353 (2.09e-9)
	5000	0.4661 (3.39e-1)	0.5995 (6.10e-2)	0.0778 (3.96e-3)	0.6804 (3.98e-9)
	25000	0.3875 (5.94e-1)	0.0566 (4.45e-4)	0.0092 (2.28e-5)	0.1807 (3.86e-8)

Note: Table entries report the sample mean (and variance) of the estimated squared gradient norm $\|\nabla f(\bar{x}^*)\|^2$ evaluated using a test sample of size $K = 75,000$ .

Across all settings, 2-RSG reduces variance over 20 runs by up to three orders of magnitude compared to RSG. 2-RSG-V achieves the lowest squared gradient norm and substantially lower classification error rates than MD-SA, showing that simple trajectory averaging fails to yield near-stationary solutions for nonconvex stochastic objectives.

Coverage note — Omitted the numerical tables for the convex least squares and (s, S) inventory control problems because their empirical findings mirror those reported in the nonconvex SVM knowl, and intermediate martingale inequality proofs.

References

1.S. Andrad'ottir. A review of simulation optimization techniques. Proceedings of the 1998 Winter Simulation Conference, pages 151–158.
2.C. Cartis, N. I. M. Gould, and Ph. L. Toint. On the complexity of steepest descent, newtons and regularized newtons methods for nonconvex unconstrained optimization. SIAM Journal on Optimization, 20(6):2833–2852, 2010.
3.C. Cartis, N. I. M. Gould, and Ph. L. Toint. On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization. SIAM Journal on Optimization, 22:66–86, 2012.
4.K.L. Chung. On a stochastic approximation method. Annals of Mathematical Statistics, pages 463–483, 1954.
5.A. R. Conn, K. Scheinberg, and L. N. Vicente. Introduction to Derivative-Free Optimization. SIAM, Philadelphia, 2009.
6.J. C. Duchi, P. L. Bartlett, and M. J. Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22:674–701, 2012.
7.M. Fu. Optimization for simulation: Theory vs. practice. INFORMS Journal on Computing, 14:192–215, 2002.
8.M.C. Fu. Gradient estimation. In S. G. Henderson and B. L. Nelson, editors, Handbooks in Operations Research and Management Science: Simulation, page 575616. Elsevier.
9.R. Garmanjani and L. N. Vicente. Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization. IMA Journal of Numerical Analysis, 2012. to appear.
10.S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms. Technical report, 2010. SIAM Journal on Optimization (under second-round review).
11.S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, I: a generic algorithmic framework. SIAM Journal on Optimization, 22:1469–1492, 2012.
12.S. Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. Technical report, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA, June 2012. E-print available at: http://www.optimization-online.org.
13.P. Glasserman. Gradient Estimation via Perturbation Analysis. Kluwer Academic Publishers, Boston,Massachusetts, 2003.
14.A. Juditsky, A. Nazin, A. B. Tsybakov, and N. Vayatis. Recursive aggregation of estimators via the mirror descent algorithm with average. Problems of Information Transmission, 41:n.4, 2005.
15.A. Juditsky and A. Nemirovski. Large deviations of vector-valued martingales in 2-smooth normed spaces. Manuscript, Georgia Institute of Technology, Atlanta, GA, 2008. E-print: www2.isye.gatech.edu/∼ nemirovs/LargeDevSubmitted.pdf.
16.A. Juditsky, P. Rigollet, and A. B. Tsybakov. Learning by mirror averaging. Annals of Statistics, 36:2183–2206, 2008.
17.A. J. Kleywegt, A. Shapiro, and T. Homem de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12:479–502, 2001.
18.G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1):365–397, 2012.
19.G. Lan, A. Nemirovski, and A. Shapiro. Validation analysis of mirror descent stochastic approximation method. Mathematical Programming, 134:425–458, 2012.
20.P. L'Ecuyer. A unified view of the IPA, SF, and LR gradient estimation techniques. Management Science, 36(11):1364–1383, 1990.
21.T. Leeuwen, M. Schmidt, M. Freidlander, and F. Herrmann. A hybrid stochastic-deterministic optimization method for waveform inversion. Manuscript, University of British Columbia, Vancouver, January 2011.
22.J. Mairal, F. Bach, J. Ponce, and G. Sapiro. Online dictionary learning for sparse coding. In In ICML, pages 689–696, 2009.
23.L. Mason, J. Baxter, P. Bartlett, and M. Frean. Boosting algorithms as gradient descent in function space. Proc. NIPS, 12:512–518, 1999.
24.A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19:1574–1609, 2009.
25.A. Nemirovski and D. Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV, 1983.
26.Y. E. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence $O(1/k^2)$ . Doklady AN SSSR, 269:543–547, 1983.
27.Y. E. Nesterov. Introductory Lectures on Convex Optimization: a basic course. Kluwer Academic Publishers, Massachusetts, 2004.
28.Y. E. Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Programming, 120:221–259, 2006.
29.Y. E. Nesterov. Random gradient-free minimization of convex functions. Technical report, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain, January 2010.
30.Y. E. Nesterov and J. P. Vial. Confidence level solutions for stochastic programming. 2000.
31.J. Nocedal and S. J. Wright. Numerical optimization. Springer-Verlag, New York, USA, 1999.
32.B.T. Polyak. New stochastic approximation type procedures. Automat. i Telemekh., 7:98–107, 1990.
33.B.T. Polyak and A.B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM J. Control and Optimization, 30:838–855, 1992.
34.H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400–407, 1951.
35.R. T. Rockafellar and R. J.-B. Wets. Variational analysis, ser. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1998.
36.R.Y. Rubinstein and A. Shapiro. Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method. John Wiley & Sons, 1993.
37.A. Sartenaer S. Gratton and Ph. L. Toint. Recursive trust-region methods for multiscale nonlinear optimization. SIAM Journal on Optimization, 19:414–444, 2008.
38.J. Sacks. Asymptotic distribution of stochastic approximation. Annals of Mathematical Statistics, 29:373–409, 1958.
39.A. Shapiro. Monte carlo sampling methods. In A. Ruszczyński and A. Shapiro, editors, Stochastic Programming. North-Holland Publishing Company, Amsterdam, 2003.
40.J.C. Spall. Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. John Wiley, Hoboken, NJ, 2003.
41.L. N. Vicente. Worst case complexity of direct search. EURO Journal on Computational Optimization, 2012. to appear.
42.R. P. Sadowski W. D. Kelton and D. T. Sturrock. Simulation with Arena. McGraw-Hill, New York, fourth edition, 2007.
43.F. Yousefian, A. Nedic, and U. V. Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48:56–67, 2012.

Citation

MLA

Ghadimi, S., and G. Lan. “Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming”. arXiv, 2013, http://arxiv.org/abs/1309.5549v1.

APA

Ghadimi, S., & Lan, G. (2013). Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming. arXiv. http://arxiv.org/abs/1309.5549v1

Chicago

Ghadimi, S., and G. Lan. 2013. “Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming”. arXiv. http://arxiv.org/abs/1309.5549v1.

Harvard

Ghadimi, S. and Lan, G. (2013) “Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1309.5549v1.

Vancouver

1. Ghadimi S, Lan G (2013) Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming. arXiv

BibTeX

@article{ghadimi2013stochastic,
  title = {Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming},
  author = {Ghadimi, Saeed and Lan, Guanghui},
  year = {2013},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1309.5549v1},
  eprint = {1309.5549}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Randomized Stochastic Gradient Method

Knowl 2 — Convergence Rate and Complexity of the RSG Method

Knowl 3 — Two-Phase Randomized Stochastic Gradient Method

Knowl 4 — High-Probability Oracle Complexity of the 2-RSG Method

Knowl 5 — Randomized Stochastic Gradient Free Method

Knowl 6 — Convergence Rate and Complexity of the RSGF Method

Knowl 7 — Two-Phase Randomized Stochastic Gradient Free Method and Complexity

Knowl 8 — Gaussian Smoothing Gradient Approximations for Zeroth-Order Optimization

Knowl 9 — Trajectory-Sampled Two-Phase Method (2-RSG-V)

Knowl 10 — Performance of Stochastic First-Order Methods on Nonconvex Support Vector Machines

References

Citation

BibTeX

Access the Paper