Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các thích ứng đa cấp tổng quát cho các thuật toán xấp xỉ ngẫu nhiên loại Robbins–Monro và Polyak–Ruppert
Tóm tắt
Trong bài báo này, chúng tôi trình bày và phân tích các thích ứng đa cấp mới của các thuật toán xấp xỉ ngẫu nhiên cổ điển để tính toán một cực tiểu của một hàm $$f:D \rightarrow {{\mathbb {R}}}^d$$ được định nghĩa trên một miền lồi $$D\subset {{\mathbb {R}}}^d$$, hàm này được cho dưới dạng một họ tham số của các kỳ vọng. Phân tích về sai số và chi phí tính toán của phương pháp chúng tôi dựa trên các giả định tương tự như được sử dụng trong Giles (Oper Res 56(3):607–617, 2008) cho việc tính toán một kỳ vọng đơn. Thêm vào đó, chúng tôi thực sự chỉ yêu cầu hàm f thoả mãn một thuộc tính co giãn cổ điển từ lý thuyết xấp xỉ ngẫu nhiên. Dưới các giả định này, chúng tôi xác lập các giới hạn sai số trong trung bình bậc p cho các phương pháp Robbins–Monro và Polyak–Ruppert đa cấp của chúng tôi mà giảm xuống theo thời gian tính toán nhanh như các giới hạn sai số cổ điển cho các xấp xỉ Monte Carlo đa cấp của các kỳ vọng đơn mà được biết đến từ Giles (Oper Res 56(3):607–617, 2008). Phương pháp của chúng tôi là phổ quát ở chỗ khi có các triển khai đa cấp cho một ứng dụng cụ thể, việc triển khai thuật toán xấp xỉ ngẫu nhiên tương ứng là rất đơn giản.
Từ khóa
#xấp xỉ ngẫu nhiên; Robbins-Monro; Polyak-Ruppert; sai số; kỳ vọng; Monte Carlo đa cấpTài liệu tham khảo
Benveniste, A., Métivier, M., Priouret, P.: Adaptive Algorithms and Stochastic Approximations. Volume 22 of Applications of Mathematics (New York), vol. 22. Springer, Berlin (1990)
Duflo, M.: Algorithmes Stochastiques. Volume 23 of Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 23. Springer, Berlin (1996)
Frikha, N.: Multi-level stochastic approximation algorithms. Ann. Appl. Probab. 26, 933–985 (2016)
Gaposhkin, V.F., Krasulina, T.P.: On the law of the iterated logarithm in stochastic approximation processes. Theory Probab. Appl. 19(4), 844–850 (1974)
Giles, M.B.: Multilevel Monte Carlo path simulation. Oper. Res. 56(3), 607–617 (2008)
Heinrich, S.: Multilevel Monte Carlo methods. In: Margenov, S., Waśniewski, J., Yalamov, P. (eds.) Large-Scale Scientific Computing, pp. 58–67. Springer, Berlin (2001)
Kushner, H.J., Yang, J.: Stochastic approximation with averaging of the iterates: optimal asymptotic rate of convergence for general processes. SIAM J. Control Optim. 31(4), 1045–1062 (1993)
Kushner, H.J., Yin, G.G.: Stochastic Approximation and Recursive Algorithms and Applications, Volume 35 of Applications of Mathematics (New York). Stochastic Modelling and Applied Probability, 2nd edn. Springer, New York (2003)
Lai, T.L.: Stochastic approximation. Ann. Stat. 31(2), 391–406 (2003). Dedicated to the memory of Herbert E. Robbins
Lai, T.L., Robbins, H.: Limit theorems for weighted sums and stochastic approximation processes. Proc. Nat. Acad. Sci. U.S.A. 75, 1068–1070 (1978)
Le Breton, A., Novikov, A.: Some results about averaging in stochastic approximation. Metrika 42(3–4):153–171 (1995). Second International Conference on Mathematical Statistics (Smolenice Castle, 1994)
Ljung, L., Pflug, G., Walk, H.: Stochastic Approximation and Optimization of Random Systems. Volume 17 of DMV Seminar, vol. 17. Birkhäuser Verlag, Basel (1992)
Nualart, D.: The Malliavin Calculus and Related Topics. Probability and Its Applications (New York), 2nd edn. Springer, Berlin (2006)
Pelletier, M.: On the almost sure asymptotic behaviour of stochastic algorithms. Stoch. Process. Appl. 78(2), 217–244 (1998)
Pelletier, M.: Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab. 8(1), 10–44 (1998)
Polyak, B.T.: A new method of stochastic approximation type. Avtomat. i Telemekh. 51(7), 937–1008 (1998)
Robbins, H., Monro, S.: A stochastic approximation method. Ann. Math. Stat. 22, 400–407 (1951)
Ruppert, D.: Almost sure approximations to the Robbins-Monro and Kiefer-Wolfowitz processes with dependent noise. Ann. Probab. 10, 178–187 (1982)
Ruppert, D.: Stochastic Approximation. In: Ghosh, B.K., Sen, P.K. (eds.) Handbook of Sequential Analysis. Volume 118 of Statist. Textbooks Monogr., pp. 503–529. Dekker, New York (1991)