Gradient-based algorithms for zeroth-order optimization
Preface
Abstract
This book 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 quickly summarize the basic material for this text. A large portion of this work is driven by our own contributions to this area.
This monograph is written with the idea of providing a self-contained introduction to stochastic gradient algorithms for solving a zeroth-order optimization problem. Towards this goal, we have included a detailed introduction to stochastic approximation which provides the basic framework for the analysis of incremental update algorithms with noise, that indeed form the backbone of algorithms in areas such as reinforcement learning, and stochastic optimization with unbiased as well as biased gradient information. We provide a detailed coverage of zeroth-order gradient estimation procedures, including classic approaches such as simultaneous perturbation stochastic approximation (SPSA), smoothed functional (SF), as well as more recent approaches dealt with in the literature. The convergence analysis that we provide includes both asymptotic guarantees via the ordinary differential equation (ODE) and differential inclusion (DI) approaches, as well as non-asymptotic bounds. The convergence analyses should be of interest to students as well as researchers working in the broad area of stochastic optimization and machine learning.
Figure 1 provides a visual depiction of the dependencies between the individual chapters and appendices in the book.
Figure 1: A schematic representation of the dependencies between the chapters and appendices in the book.
We now provide a few guidelines on how to read this book.
If you are an expert researcher well-versed in the field of stochastic approximation, then we suggest reading Chapters 3–5. These chapters cover (i) gradient estimation in a zeroth-order setting, where only noisy function measurements are available; and (ii) asymptotic as well as non-asymptotic analysis of stochastic gradient algorithms with zeroth-order gradient estimates. If you find the material in these chapters interesting, then you could go further to stochastic Newton algorithms with zeroth-order Hessian estimates. These topics are covered in Chapter 6. You could also check out Chapter 7, which describes variants of stochastic gradient/Newton algorithms designed to escape saddle points and converge to local optima.
If you are student who has done a first course in probability, and someone who would like to conduct research in the area of zeroth-order optimization, then we suggest you pick up the background material covered in the appendices, in particular, ODEs and differential inclusions (Appendix A), conditional expectations and martingales (Appendix B) and smoothness/convexity (Appendix D). Thereafter, we recommend understanding stochastic approximation, gradient estimation and analysis of stochastic gradient algorithms in that order from Chapters 2–4. Introduction to stochastic Newton methods and their analyses, which form the content of subsequent chapters, could be done after the zeroth-order gradient algorithms/analyses are covered.
If you are also a reinforcement learning (RL) researcher, then the material covered in Chapter 8 could be of interest. In this chapter, we present zeroth-order variations of the well-known REINFORCE policy gradient method. In particular, we establish that such zeroth-order variants are competent and in many RL applications, REINFORCE style gradient estimation is not feasible, making zeroth-order schemes more amenable. One such setting that we cover is risk-sensitive RL, where the objective is not the usual value function, which is an expected value. Instead, we consider alternate functionals of the distribution and describe zeroth-order policy gradient algorithms for optimizing such functionals.
From a teaching viewpoint, the material in this book can be utilized for a semester-long course, with an optional followup course on the shorter side, say one-quarter. In the former course, the background material on ODEs and differential inclusions, conditional expectations and martingales and smoothness and convexity could be introduced first. These correspond to Appendices A, B and D. Next, the content in Chapters 1–5 on stochastic gradient algorithms/analyses could be covered. Sections 2.6 and 2.7 could be skipped in this course. The followup course could cover Chapters 6–8 on the stochastic Newton algorithms/analyses and RL applications as well as the skipped sections mentioned above.
We would like to thank Praneeth Netrapalli for useful inputs about perturbed gradient descent algorithm, and Aditya Mahajan for useful discussions on two timescale stochastic approximation. We would like to thank our students Soumen Pachal, Sumedh Gupte, Anmol Panda, Shaun Mathew and Ayman Akhter for pointing out typos and minor errors in the earlier versions of this manuscript. Part of this work was supported through a J. C. Bose Fellowship, Project No. DFTM/ 02/ 3125/M/04/AIR-04 from DRDO under DIA-RCOE, the Walmart Center for Tech Excellence at IISc (CSR Grant WMGT-23-0001), and the RBCCPS, IISc. A portion of this book was written when the first author was visiting the Centre for Machine Intelligence and Data Sciences (C-MInDS) at the Indian Institute of Technology Bombay.
Citing this book
@article{prashanth2025gradient,
title={Gradient-based algorithms for zeroth-order optimization},
author={Prashanth, L.A. and Bhatnagar, Shalabh},
journal={Foundations and Trends{\textregistered} in Optimization},
volume={8},
number={1--3},
pages={1--332},
year={2025},
publisher={Now Publishers, Inc.}
}