Source-linked AI summary
Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
Saeed Ghadimi, Guanghui Lan
TL;DR
The paper addresses stochastic programming with possibly nonconvex objectives and unknown convexity in simulation-based settings. It develops RSG and related gradient-free methods, establishes complexity results, and improves large-deviation properties through post-optimization.
Problem
Existing stochastic approximation algorithms rely on convexity, while simulation-based objectives may be nonconvex or have unknown convexity.
Method
The paper develops the randomized stochastic gradient method, a two-phase post-optimization variant, and Gaussian-smoothed randomized stochastic gradient-free methods.
Results
The methods receive complexity bounds for nonconvex stochastic programming, nearly optimal convergence in convex cases, improved large-deviation properties, and O(n/ǫ2) gradient-free complexity results.
Takeaways & Limitations
The framework extends stochastic approximation to possibly nonconvex stochastic programs and to simulation-based problems with only stochastic zeroth-order information.
Takeaways & Limitations
The direct RSGF approach does not provide an explicit variance bound or guidance for choosing the smoothing parameter µ.
Abstract
from arXiv · showhide
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.
1. Introduction.
The paper develops stochastic approximation methods for nonlinear stochastic programs with possibly nonconvex objectives and noisy first-order information. It introduces randomized gradient methods, extends them to zeroth-order simulation-based optimization, and establishes complexity results for these settings.
- Existing stochastic approximation convergence results generally require convexity, leaving more general possibly nonconvex stochastic programs unaddressed.
- The paper studies unconstrained nonlinear programs with differentiable, bounded-below objectives whose gradients are accessed through a stochastic first-order oracle.
- The stochastic oracle produces an unbiased gradient estimator with bounded variance, without requiring the sampled random variables to be mutually independent.
- The two-phase randomized stochastic gradient method evaluates a short list of solutions from independent runs to improve the RSG method’s large-deviation properties and reliability.
- The gradient-free RSGF method achieves O(n/ǫ^2) iteration complexity for nonconvex stationary-point finding and smooth convex objective-gap guarantees.The paper presents this as a complexity result for stochastic zeroth-order simulation-based optimization; the convex guarantee is also O(n/ǫ^2).
2. Stochastic first-order methods.
The RSG method uses randomized termination or output selection to analyze smooth stochastic programs without requiring convexity, while 2-RSG improves large-deviation complexity through post-optimization. The method also retains nearly optimal convergence in convex problems.
- The randomized stochastic gradient method: RSG introduces randomized iteration selection into stochastic approximation, enabling convergence analysis for both convex and nonconvex stochastic programs.The method permits noise to depend on the search sequence, unlike existing approaches whose convergence requires convexity and often independence assumptions.
- The randomized stochastic gradient method: The algorithm repeatedly queries a stochastic first-order oracle, updates iterates using chosen stepsizes, and outputs the iterate indexed by a random variable R.Its input includes an initial point, iteration limit, stepsizes, and a probability mass function supported on the iteration indices.
- The randomized stochastic gradient method: Under Assumption A1, Theorem 2.1 establishes expected convergence bounds for nonconvex problems and corresponding bounds when the problem is convex.The convex result additionally assumes an optimal solution x∗; the bounds use expectations over the random iteration index and generated noise.
- The randomized stochastic gradient method: A practical limitation is that RSG requires estimating the smoothness constant L to bound stepsizes and potentially select the iteration distribution.Exact objective values and gradients are unavailable in the stochastic setting, making line-search procedures more difficult, although highly accurate estimates of L are unnecessary.
- The randomized stochastic gradient method: The RSG method has a nearly optimal convergence rate for smooth convex stochastic programming, because its unimprovable second term matches the optimal bound while its first term can be improved.The paper also notes that the O(1/N) term for nonconvex gradient descent is unimprovable, though this does not establish tightness for all first-order methods.
- A two-phase randomized stochastic gradient method: 2-RSG generates candidate solutions through independent RSG runs and selects among them in a post-optimization phase, improving the complexity bound for an (ε, Λ)-solution.Theorem 2.4 and its corollary provide parameter settings and complexity bounds for the two-phase procedure.
3. Stochastic zeroth-order methods.
The paper adapts randomized stochastic gradient methods to settings where only noisy function values are available, using Gaussian smoothing and stochastic gradient-free estimators. It derives convergence and complexity results for nonconvex and convex problems, then extends the method with post-optimization runs to improve reliability.
- RSGF method: Gaussian convolution produces a smooth approximation fµ of the objective, enabling gradient-based analysis of zeroth-order estimates.The smoothing parameter µ controls the approximation, while the Gaussian distribution supplies the convolution.
- RSGF method: The RSG method is modified into RSGF to solve stochastic optimization problems using only stochastic zeroth-order information.The method replaces stochastic gradients with gradient-free estimates based on a smoothed objective.
- RSGF method: Gµ(x, ξ, u) is an unbiased estimator of ∇fµ(x), but its variance bound and suitable smoothing parameter are not explicitly known in the basic approach.The unspecified smoothing choice is identified as critical for implementing RSGF.
- Convergence and complexity: Refined convergence results for RSGF follow by combining approximation results for F(·, ξk) with a convergence analysis different from the first-order theorem.The theorem requires step sizes satisfying γk < 1/[2(n + 4)L] and additional assumptions.
- Convergence and complexity: O(n/ε^2) iterations suffice for an ε-solution in both nonconvex and convex stochastic settings, while σ = 0 reduces the complexity to O(n/ε).For convex problems, the result concerns expected objective gap; the deterministic reduction is compared with derivative-free random search.
- Two-phase extension: The 2-RSGF method adds a post-optimization phase that evaluates outputs from several independent RSGF runs to improve large-deviation guarantees.Its convergence and (ε, Λ)-solution complexity are summarized in Theorem 3.4.
4. Concluding remarks.
The paper develops stochastic approximation methods for unconstrained nonlinear programs with noisy first-order information and specializes them to simulation-based optimization with stochastic zeroth-order information.
- Concluding remarks: The methods establish complexity results for computing ε-solutions and achieve nearly optimal convergence rates when the problem is convex.The paper also introduces post-optimization to improve the randomized stochastic gradient method’s large-deviation properties.
- Concluding remarks: Gradient-free methods for smooth convex stochastic programming can have weaker dimension dependence than methods for more general nonsmooth convex problems.This conclusion is stated for the specialized simulation-based optimization setting.