×

A companion for the Kiefer-Wolfowitz-Blum stochastic approximation algorithm. (English) Zbl 1209.62191

Summary: A stochastic algorithm for the recursive approximation of the location \(\theta\) of a maximum of a regression function was introduced by J. Kiefer and J. Wolfowitz [Ann. Math. Stat. 23, 462–466 (1952; Zbl 0049.36601)] in the univariate framework, and by J. R. Blum [Ann. Math. Stat. 25, 737–744 (1954; Zbl 0056.38305)] in the multivariate case. The aim of this paper is to provide a companion algorithm to the Kiefer-Wolfowitz-Blum algorithm, which allows one to simultaneously recursively approximate the size \(\mu\) of the maximum of the regression function. A precise study of the joint weak convergence rate of both algorithms is given; it turns out that, unlike the location of the maximum, the size of the maximum can be approximated by an algorithm which converges at the parametric rate. Moreover, averaging leads to an asymptotically efficient algorithm for the approximation of the couple \((\theta,\mu)\).

MSC:

62L20 Stochastic approximation
62G08 Nonparametric regression and quantile regression
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Blum, J. R. (1954). Multidimensional stochastic approximation methods. Ann. Math. Statist. 25 737–744. · Zbl 0056.38305
[2] Bojanic, R. and Seneta, E. (1973). A unified theory of regularly varying sequences. Math. Z. 134 91–106. · Zbl 0256.40002
[3] Chen, H. (1988). Lower rate of convergence for locating a maximum of a function. Ann. Statist. 16 1330–1334. · Zbl 0651.62034
[4] Chen, H. F., Duncan, T. E. and Pasik-Duncan, B. (1999). A Kiefer–Wolfowitz algorithm with randomized differences. IEEE Trans. Automat. Control 44 442–453. · Zbl 1056.93622
[5] Delyon, B. and Juditsky, A. B. (1992). Stochastic optimization with averaging of trajectories. Stochastics Stochastics Rep. 39 107–118. · Zbl 0765.93081
[6] Dippon, J. (2003). Accelerated randomized stochastic optimization. Ann. Statist. 31 1260–1281. · Zbl 1105.62370
[7] Dippon, J. and Renz, J. (1996). Weighted means of processes in stochastic approximation. Math. Methods Statist. 5 32–60. · Zbl 0858.62070
[8] Dippon, J. and Renz, J. (1997). Weighted means in stochastic approximation of minima. SIAM J. Control Optim. 35 1811–1827. · Zbl 0885.62094
[9] Duflo, M. (1996). Algorithmes Stochastiques . Springer, Berlin. · Zbl 0882.60001
[10] Duflo, M. (1997). Random Iterative Models . Springer, Berlin. · Zbl 0868.62069
[11] Fabian, V. (1967). Stochastic approximation of minima with improved asymptotic speed. Ann. Math. Statist. 38 191–200. · Zbl 0147.18003
[12] Galambos, J. and Seneta, E. (1973). Regularly varying sequences. Proc. Amer. Math. Soc. 41 110–116. · Zbl 0247.26002
[13] Hall, P. and Heyde, C. C. (1980). Martingale Limit Theory and Its Application . Academic Press, New York. · Zbl 0462.60045
[14] Hall, P. and Molchanov, I. (2003). Sequential methods for design-adaptive estimation of discontinuities in regression curves and surfaces. Ann. Statist. 31 921–941. · Zbl 1028.62069
[15] Kiefer, J. and Wolfowitz, J. (1952). Stochastic estimation of the maximum of a regression function. Ann. Math. Statist. 23 462–466. · Zbl 0049.36601
[16] Koval, V. and Schwabe, R. (1998). Exact bounds for the rate of convergence in general stochastic approximation procedures. Stochastic Anal. Appl. 16 501–515. · Zbl 0901.62099
[17] Kushner, H. J. and Clark, D. S. (1978). Stochastic Approximation Methods for Constrained and Unconstrained Systems . Springer, New York. · Zbl 0381.60004
[18] Kushner, H. J. and Yang, J. (1993). Stochastic approximation with averaging of the iterates: Optimal asymptotic rate of convergence for general processes. SIAM J. Control Optim. 31 1045–1062. · Zbl 0788.62078
[19] Le Breton, A. (1993). About the averaging approach in Gaussian schemes for stochastic approximation. Math. Methods Statist. 2 295–315. · Zbl 0798.62086
[20] Le Breton, A. and Novikov, A. (1995). Some results about averaging in stochastic approximation. Metrika 42 153–171. · Zbl 0834.62074
[21] Ljung, L. (1977). Analysis of recursive stochastic algorithms. IEEE Trans. Automat. Control 22 551–575. · Zbl 0362.93031
[22] Ljung, L. (1978). Strong convergence of a stochastic approximation algorithm. Ann. Statist. 6 680–696. · Zbl 0402.62060
[23] Ljung, L., Pflug, G. and Walk, H. (1992). Stochastic Approximation and Optimization of Random Systems . Birkhäuser, Basel. · Zbl 0747.62090
[24] Mokkadem, A. and Pelletier, M. (2005). The compact law of the iterated logarithm for multivariate stochastic approximation algorithms. Stochastic Anal. Appl. 23 181–203. · Zbl 1066.60034
[25] Nevels’on, M. B. and Has’minskii, R. Z. (1976). Stochastic Approximation and Recursive Estimation . Amer. Math. Soc., Providence, RI.
[26] Pelletier, M. (1998). On the almost sure asymptotic behaviour of stochastic algorithms. Stochastic Process. Appl. 78 217–244. · Zbl 0926.62072
[27] Pelletier, M. (2000). Asymptotic almost sure efficiency of averaged stochastic algorithms. SIAM J. Control Optim. 39 49–72. · Zbl 1015.60028
[28] Polyak, B. T. (1990). New method of stochastic approximation type. Automat. Remote Control 51 937–946. · Zbl 0737.93080
[29] Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30 838–855. · Zbl 0762.62022
[30] Polyak, B. T. and Tsybakov, A. B. (1990). Optimal orders of accuracy for search algorithms of stochastic optimization. Problems Inform. Transmission 26 126–133. · Zbl 0712.90073
[31] Ruppert, D. (1982). Almost sure approximations to the Robbins–Monro and Kiefer–Wolfowitz processes with dependent noise. Ann. Probab. 10 178–187. · Zbl 0485.62083
[32] Ruppert, D. (1991). Stochastic approximation. In Handbook of Sequential Analysis (B. K. Ghosh and P. K. Sen, eds.) 503–529. Dekker, New York.
[33] Spall, J. C. (1988). A stochastic approximation algorithm for large-dimensional systems in the Kiefer–Wolfowitz setting. In Proc. 27th IEEE Conference on Decision and Control 1544–1548. IEEE Press, New York.
[34] Spall, J. C. (1997). A one-measurement form of simultaneous perturbation stochastic approximation. Automatica J. IFAC 33 109–112. · Zbl 0867.93086
[35] Yin, G. (1991). On extensions of Polyak’s averaging approach to stochastic approximation. Stochastics Stochastics Rep. 36 245–264. · Zbl 0749.62055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.