Gradient-Based Algorithms for Zeroth-Order Optimization

This monograph deals with methods for stochastic or data-driven optimization. The overall goal of these methods is to minimize a certain parameter-dependent objective function that for any parameter value is an expectation of a noisy sample performance objective whose measurement can be made from a real system or a simulation device depending on the setting used. A class of model-free approaches based on stochastic approximation is presented which involve random search procedures to efficiently make use of the noisy observations. The idea here is to simply estimate the minima of the expected objective via an incremental-update or recursive procedure and not to estimate the whole objective function itself. Both asymptotic as well as finite sample analyses of the procedures used for convex as well as non-convex objectives are presented.

The monograph also includes algorithms that either estimate the gradient in gradient-based schemes or estimate both the gradient and the Hessian in Newton-type procedures using random direction approaches involving noisy function measurements. Hence the class of approaches studied fall under the broad category of zeroth order optimization methods. Both asymptotic convergence guarantees in the general setup as well as asymptotic normality results for various algorithms are presented, and also provided is an introduction to stochastic recursive inclusions and their asymptotic convergence analysis. This is necessitated because many of these settings involve set-valued maps for any given parameter. Finally, several interesting applications of these methods in the domain of reinforcement learning are included, and the appendices at the end quickly summarize the basic material for this text.