General Bounds and Finite-Time Improvement for the Kiefer-Wolfowitz Stochastic Approximation Algorithm

Mark Broadie (), Deniz Cicek () and Assaf Zeevi ()
Additional contact information
Mark Broadie: Graduate School of Business, Columbia University, New York, New York 10027
Deniz Cicek: Graduate School of Business, Columbia University, New York, New York 10027
Assaf Zeevi: Graduate School of Business, Columbia University, New York, New York 10027

Operations Research, 2011, vol. 59, issue 5, 1211-1224

Abstract: We consider the Kiefer-Wolfowitz (KW) stochastic approximation algorithm and derive general upper bounds on its mean-squared error. The bounds are established using an elementary induction argument and phrased directly in the terms of tuning sequences of the algorithm. From this we deduce the nonnecessity of one of the main assumptions imposed on the tuning sequences by Kiefer and Wolfowitz [Kiefer, J., J. Wolfowitz. 1952. Stochastic estimation of the maximum of a regression function. Ann. Math. Statist. 23 (3) 462--466] and essentially all subsequent literature. The optimal choice of sequences is derived for various cases of interest, and an adaptive version of the KW algorithm, scaled-and-shifted KW (or SSKW), is proposed with the aim of improving its finite-time behavior. The key idea is to dynamically scale and shift the tuning sequences to better match them with characteristics of the unknown function and noise level, and thus improve algorithm performance. Numerical results are provided that illustrate that the proposed algorithm retains the convergence properties of the original KW algorithm while dramatically improving its performance in some cases.

Keywords: stochastic optimization; stochastic approximation; the Kiefer-Wolfowitz algorithm; mean-squared-error convergence; finite-time improvement (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0970 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:5:p:1211-1224

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().