Gradient-Based Algorithms for Zeroth-Order Optimization
By Prashanth L. A., Department of Computer Science and Engineering, Indian Institute of Technology Madras, India, prashla@cse.iitm.ac.in | Shalabh Bhatnagar, Department of Computer Science and Automation, Indian Institute of Science Bangalore, India, shalabh@iisc.ac.in
Abstract
This monograph deals with methods for stochastic or data-driven optimization. The overall goal in 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. We present a class of model-free approaches based on stochastic approximation 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. We provide both asymptotic as well as finite sample analyses of the procedures used for convex as well as non-convex objectives.
We present 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 that we study fall under the broad category of zeroth order optimization methods. We provide both asymptotic convergence guarantees in the general setup as well as asymptotic normality results for various algorithms. We also provide an introduction to stochastic recursive inclusions as well as their asymptotic convergence analysis. This is necessitated because many of these settings involve set-valued maps for any given parameter. We also present a couple of interesting applications of these methods in the domain of reinforcement learning. Five appendices at the end of this work quickly summarize the basic material. A large portion of this work is driven by our own contributions to this area.
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.
