IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v59y2011i5p1211-1224.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Mark Broadie & Deniz Cicek & Assaf Zeevi, 2011. "General Bounds and Finite-Time Improvement for the Kiefer-Wolfowitz Stochastic Approximation Algorithm," Operations Research, INFORMS, vol. 59(5), pages 1211-1224, October.
    • Handle: RePEc:inm:oropre:v:59:y:2011:i:5:p:1211-1224
    DOI: 10.1287/opre.1110.0970
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.0970
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.0970?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Powell, Warren B., 2019. "A unified framework for stochastic optimization," European Journal of Operational Research, Elsevier, vol. 275(3), pages 795-821.
    2. Boxiao Chen & Xiuli Chao & Cong Shi, 2021. "Nonparametric Learning Algorithms for Joint Pricing and Inventory Control with Lost Sales and Censored Demand," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 726-756, May.
    3. Aleksandrina Goeva & Henry Lam & Huajie Qian & Bo Zhang, 2019. "Optimization-Based Calibration of Simulation Input Models," Operations Research, INFORMS, vol. 67(5), pages 1362-1382, September.
    4. Takayuki Wada & Yasumasa Fujisaki, 2016. "Stopping Rules for Optimization Algorithms Based on Stochastic Approximation," Journal of Optimization Theory and Applications, Springer, vol. 169(2), pages 568-586, May.
    5. Kim, Sojung & Weber, Stefan, 2022. "Simulation methods for robust risk assessment and the distorted mix approach," European Journal of Operational Research, Elsevier, vol. 298(1), pages 380-398.
    6. Thomas Loots & Arnoud V. den Boer, 2023. "Data‐driven collusion and competition in a pricing duopoly with multinomial logit demand," Production and Operations Management, Production and Operations Management Society, vol. 32(4), pages 1169-1186, April.
    7. Josef Broder & Paat Rusmevichientong, 2012. "Dynamic Pricing Under a General Parametric Choice Model," Operations Research, INFORMS, vol. 60(4), pages 965-980, August.
    8. Zhaolin Hu & Dali Zhang, 2018. "Utility‐based shortfall risk: Efficient computations via Monte Carlo," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(5), pages 378-392, August.
    9. Arel-Bundock, Vincent, 2013. "A solution to the weak instrument bias in 2SLS estimation: Indirect inference with stochastic approximation," Economics Letters, Elsevier, vol. 120(3), pages 495-498.
    10. Sojung Kim & Stefan Weber, 2020. "Simulation Methods for Robust Risk Assessment and the Distorted Mix Approach," Papers 2009.03653, arXiv.org, revised Jan 2022.
    11. Ye Chen & Ilya O. Ryzhov, 2020. "Technical Note—Consistency Analysis of Sequential Learning Under Approximate Bayesian Inference," Operations Research, INFORMS, vol. 68(1), pages 295-307, January.
    12. Steven Kou & Xianhua Peng & Xingbo Xu, 2016. "EM Algorithm and Stochastic Control in Economics," Papers 1611.01767, arXiv.org.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:59:y:2011:i:5:p:1211-1224. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.