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

Slides

Click here