Simultaneous perturbation methods for stochastic non-convex optimization
Tutorial Description
Stochastic gradient algorithms form the basis of several optimization approaches, and find wide applicability across various engineering disciplines such as machine learning, communication engineering, signal processing and robotics. In the zeroth-order setting that we consider, an algorithm is provided noisy function measurements, and has to construct gradient estimates from these measurements. The highly efficient simultaneous perturbation method is a popular approach for gradient estimation. This tutorial presents stochastic gradient/Newton algorithms for non-convex optimization. In particular, we present several simultaneous perturbation based estimators for the gradient and Hessian. A remarkable feature of the algorithms is that they are easily implementable, do not require an explicit system model, and work with real or simulated data. The tutorial also covers applications in transportation and service systems to illustrate these points.
Tutorial Outline
Simulation optimization: problem setting, practical motivation, challenges
First-order methods: gradient estimation, (near) unbiasedness, convergence analysis
Second-order methods: Hessian estimation, (near) unbiasedness, convergence analysis
Applications: Service systems, transportation