{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T03:49:08Z","timestamp":1772941748839,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T00:00:00Z","timestamp":1611187200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T00:00:00Z","timestamp":1611187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N510129\/1"],"award-info":[{"award-number":["EP\/N510129\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["TEC2015-69868-C2-1-R ADVENTURE"],"award-info":[{"award-number":["TEC2015-69868-C2-1-R ADVENTURE"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["RTI2018-099655-B-I00 CLARA"],"award-info":[{"award-number":["RTI2018-099655-B-I00 CLARA"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007297","name":"Office of Naval Research Global","doi-asserted-by":"publisher","award":["N00014-19-1-2226"],"award-info":[{"award-number":["N00014-19-1-2226"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2021,3]]},"abstract":"Abstract<\/jats:title>Adaptive importance samplers are adaptive Monte Carlo algorithms to estimate expectations with respect to some target distribution which adapt<\/jats:italic> themselves to obtain better estimators over a sequence of iterations. Although it is straightforward to show that they have the same $$\\mathcal {O}(1\/\\sqrt{N})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \n N<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> convergence rate as standard importance samplers, where N<\/jats:italic> is the number of Monte Carlo samples, the behaviour of adaptive importance samplers over the number of iterations has been left relatively unexplored. In this work, we investigate an adaptation strategy based on convex optimisation which leads to a class of adaptive importance samplers termed optimised adaptive importance samplers<\/jats:italic> (OAIS). These samplers rely on the iterative minimisation of the $$\\chi ^2$$<\/jats:tex-math>\n \n \u03c7<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-divergence between an exponential family proposal and the target. The analysed algorithms are closely related to the class of adaptive importance samplers which minimise the variance of the weight function. We first prove non-asymptotic error bounds for the mean squared errors (MSEs) of these algorithms, which explicitly depend on the number of iterations and the number of samples together. The non-asymptotic bounds derived in this paper imply that when the target belongs to the exponential family, the $$L_2$$<\/jats:tex-math>\n \n L<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> errors of the optimised samplers converge to the optimal rate of $$\\mathcal {O}(1\/\\sqrt{N})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n \n N<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the rate of convergence in the number of iterations are explicitly provided. When the target does not<\/jats:italic> belong to the exponential family, the rate of convergence is the same but the asymptotic $$L_2$$<\/jats:tex-math>\n \n L<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> error increases by a factor $$\\sqrt{\\rho ^\\star } > 1$$<\/jats:tex-math>\n \n \n \n \u03c1<\/mml:mi>\n \u22c6<\/mml:mo>\n <\/mml:msup>\n <\/mml:msqrt>\n ><\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$\\rho ^\\star - 1$$<\/jats:tex-math>\n \n \n \u03c1<\/mml:mi>\n \u22c6<\/mml:mo>\n <\/mml:msup>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the minimum $$\\chi ^2$$<\/jats:tex-math>\n \n \u03c7<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-divergence between the target and an exponential family proposal.<\/jats:p>","DOI":"10.1007\/s11222-020-09983-1","type":"journal-article","created":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T07:02:56Z","timestamp":1611212576000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Convergence rates for optimised adaptive importance samplers"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5248-1219","authenticated-orcid":false,"given":"\u00d6mer Deniz","family":"Akyildiz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joaqu\u00edn","family":"M\u00edguez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,21]]},"reference":[{"issue":"3","key":"9983_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1214\/17-STS611","volume":"32","author":"S Agapiou","year":"2017","unstructured":"Agapiou, S., Papaspiliopoulos, O., Sanz-Alonso, D., Stuart, A.: Importance sampling: intrinsic dimension and computational cost. Stat. Sci. 32(3), 405\u2013431 (2017)","journal-title":"Stat. Sci."},{"key":"9983_CR2","unstructured":"Akyildiz, \u00d6D., Sabanis, S.: Nonasymptotic analysis of Stochastic Gradient Hamiltonian Monte Carlo under local conditions for nonconvex optimization. (2020). arXiv preprint arXiv:2002.05465"},{"issue":"1","key":"9983_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/156939604323091180","volume":"10","author":"B Arouna","year":"2004","unstructured":"Arouna, B.: Adaptative monte carlo method, a variance reduction technique. Monte Carlo Methods Appl. 10(1), 1\u201324 (2004a)","journal-title":"Monte Carlo Methods Appl."},{"issue":"2","key":"9983_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.21314\/JCF.2003.111","volume":"7","author":"B Arouna","year":"2004","unstructured":"Arouna, B.: Robbins-Monro algorithms and variance reduction in finance. J. Comput. Finance 7(2), 35\u201362 (2004b)","journal-title":"J. Comput. Finance"},{"key":"9983_CR5","unstructured":"Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning. (2016). arXiv:1606.04838"},{"issue":"3\u20134","key":"9983_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1561\/2200000050","volume":"8","author":"S Bubeck","year":"2015","unstructured":"Bubeck, S., et al.: Convex optimization: algorithms and complexity. Found. Trends\u00ae Mach. Learn. 8(3\u20134), 231\u2013357 (2015)","journal-title":"Found. Trends\u00ae Mach. Learn."},{"key":"9983_CR7","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.dsp.2015.05.014","volume":"47","author":"MF Bugallo","year":"2015","unstructured":"Bugallo, M.F., Martino, L., Corander, J.: Adaptive importance sampling in signal processing. Digit. Signal Proc. 47, 36\u201349 (2015)","journal-title":"Digit. Signal Proc."},{"issue":"4","key":"9983_CR8","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1109\/MSP.2017.2699226","volume":"34","author":"MF Bugallo","year":"2017","unstructured":"Bugallo, M.F., Elvira, V., Martino, L., Luengo, D., Miguez, J., Djuric, P.M.: Adaptive Importance Sampling: The past, the present, and the future. IEEE Signal Process. Mag. 34(4), 60\u201379 (2017)","journal-title":"IEEE Signal Process. Mag."},{"issue":"4","key":"9983_CR9","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1198\/106186004X12803","volume":"13","author":"O Capp\u00e9","year":"2004","unstructured":"Capp\u00e9, O., Guillin, A., Marin, J.M., Robert, C.P.: Population Monte Carlo. J. Comput. Graph. Stat. 13(4), 907\u2013929 (2004)","journal-title":"J. Comput. Graph. Stat."},{"issue":"4","key":"9983_CR10","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s11222-008-9059-x","volume":"18","author":"O Capp\u00e9","year":"2008","unstructured":"Capp\u00e9, O., Douc, R., Guillin, A., Marin, J.M., Robert, C.P.: Adaptive importance sampling in general mixture classes. Stat. Comput. 18(4), 447\u2013459 (2008)","journal-title":"Stat. Comput."},{"issue":"2","key":"9983_CR11","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1214\/17-AAP1326","volume":"28","author":"S Chatterjee","year":"2018","unstructured":"Chatterjee, S., Diaconis, P., et al.: The sample size required in importance sampling. Ann. Appl. Probab. 28(2), 1099\u20131135 (2018)","journal-title":"Ann. Appl. Probab."},{"issue":"4","key":"9983_CR12","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.3150\/13-BEJ545","volume":"20","author":"D Crisan","year":"2014","unstructured":"Crisan, D., M\u00edguez, J.: Particle-kernel estimation of the filter density in state-space models. Bernoulli 20(4), 1879\u20131929 (2014)","journal-title":"Bernoulli"},{"key":"9983_CR13","unstructured":"Dieng, A.B., Tran, D., Ranganath, R., Paisley, J., Blei, D.: Variational inference via $$\\chi $$-upper bound minimization. In: Advances in Neural Information Processing Systems, pp 2732\u20132741 (2017)"},{"issue":"1","key":"9983_CR14","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1214\/009053606000001154","volume":"35","author":"R Douc","year":"2007","unstructured":"Douc, R., Guillin, A., Marin, J.M., Robert, C.P.: Convergence of adaptive mixtures of importance sampling schemes. Ann. Stat. 35(1), 420\u2013448 (2007)","journal-title":"Ann. Stat."},{"key":"9983_CR15","unstructured":"Jain, P., Nagaraj, D., Netrapalli, P.: Making the Last Iterate of SGD Information Theoretically Optimal. In: Conference on Learning Theory, pp. 1752\u20131755 (2019)"},{"issue":"5","key":"9983_CR16","doi-asserted-by":"publisher","first-page":"1244","DOI":"10.1007\/s10955-016-1446-7","volume":"162","author":"HJ Kappen","year":"2016","unstructured":"Kappen, H.J., Ruiz, H.C.: Adaptive importance sampling for control and inference. J. Stat. Phys. 162(5), 1244\u20131266 (2016)","journal-title":"J. Stat. Phys."},{"issue":"2","key":"9983_CR17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s11009-007-9043-5","volume":"10","author":"R Kawai","year":"2008","unstructured":"Kawai, R.: Adaptive monte carlo variance reduction for l\u00e9vy processes with two-time-scale stochastic approximation. Methodol. Comput. Appl. Probab. 10(2), 199\u2013223 (2008)","journal-title":"Methodol. Comput. Appl. Probab."},{"issue":"4","key":"9983_CR18","doi-asserted-by":"publisher","first-page":"A1586","DOI":"10.1137\/15M1047192","volume":"39","author":"R Kawai","year":"2017","unstructured":"Kawai, R.: Acceleration on adaptive importance sampling with sample average approximation. SIAM J. Sci. Comput. 39(4), A1586\u2013A1615 (2017)","journal-title":"SIAM J. Sci. Comput."},{"issue":"4","key":"9983_CR19","doi-asserted-by":"publisher","first-page":"A2774","DOI":"10.1137\/18M1173472","volume":"40","author":"R Kawai","year":"2018","unstructured":"Kawai, R.: Optimizing adaptive importance sampling by stochastic approximation. SIAM J. Sci. Comput. 40(4), A2774\u2013A2800 (2018)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"9983_CR20","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1515\/mcma.2011.002","volume":"17","author":"B Lapeyre","year":"2011","unstructured":"Lapeyre, B., Lelong, J.: A framework for adaptive monte carlo procedures. Monte Carlo Methods Appl. 17(1), 77\u201398 (2011)","journal-title":"Monte Carlo Methods Appl."},{"key":"9983_CR21","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer, Berlin (2013)"},{"key":"9983_CR22","unstructured":"Raginsky, M., Rakhlin, A., Telgarsky, M.: Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis. In: Conference on Learning Theory, pp. 1674\u20131703 (2017)"},{"key":"9983_CR23","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1214\/aoms\/1177729586","volume":"22","author":"H Robbins","year":"1951","unstructured":"Robbins, H., Monro, S.: A stochastic approximation method. Ann. Math. Stat. 22, 400\u2013407 (1951)","journal-title":"Ann. Math. Stat."},{"key":"9983_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4145-2","volume-title":"Monte Carlo Statistical Methods","author":"CP Robert","year":"2004","unstructured":"Robert, C.P., Casella, G.: Monte Carlo Statistical Methods. Wiley, New York (2004)"},{"key":"9983_CR25","unstructured":"Ryu, E.K.: Convex optimization for Monte Carlo: Stochastic optimization for importance sampling. PhD thesis, Stanford University (2016)"},{"key":"9983_CR26","unstructured":"Ryu, E.K., Boyd, S.P. Adaptive importance sampling via stochastic convex programming. (2014). arXiv:1412.4845"},{"issue":"2","key":"9983_CR27","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1137\/16M1093549","volume":"6","author":"D Sanz-Alonso","year":"2018","unstructured":"Sanz-Alonso, D.: Importance sampling and necessary sample size: an information theory approach. SIAM\/ASA J. Uncertain. Quantif. 6(2), 867\u2013879 (2018)","journal-title":"SIAM\/ASA J. Uncertain. Quantif."},{"issue":"1\u20132","key":"9983_CR28","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s10107-016-1030-6","volume":"162","author":"M Schmidt","year":"2017","unstructured":"Schmidt, M., Le Roux, N., Bach, F.: Minimizing finite sums with the stochastic average gradient. Math. Program. 162(1\u20132), 83\u2013112 (2017)","journal-title":"Math. Program."},{"key":"9983_CR29","unstructured":"Shamir, O., Zhang, T.: Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In: International Conference on Machine Learning, pp 71\u201379 (2013)"},{"issue":"6","key":"9983_CR30","doi-asserted-by":"publisher","first-page":"3255","DOI":"10.1214\/16-AAP1272","volume":"27","author":"VB Tadi\u0107","year":"2017","unstructured":"Tadi\u0107, V.B., Doucet, A.: Asymptotic bias of stochastic gradient search. Ann. Appl. Probab. 27(6), 3255\u20133304 (2017)","journal-title":"Ann. Appl. Probab."},{"issue":"1\u20132","key":"9983_CR31","first-page":"1","volume":"1","author":"MJ Wainwright","year":"2008","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Found. Trends\u00ae Mach. Learn. 1(1\u20132), 1\u2013305 (2008)","journal-title":"Found. Trends\u00ae Mach. Learn."},{"key":"9983_CR32","unstructured":"Zhang, Y., Akyildiz, \u00d6D., Damoulas, T., Sabanis, S.: Nonasymptotic estimates for Stochastic Gradient Langevin Dynamics under local conditions in nonconvex optimization. (2019). arXiv preprint arXiv:1910.02008"}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-020-09983-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11222-020-09983-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-020-09983-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T04:44:25Z","timestamp":1615610665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11222-020-09983-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,21]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["9983"],"URL":"https:\/\/doi.org\/10.1007\/s11222-020-09983-1","relation":{},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"value":"0960-3174","type":"print"},{"value":"1573-1375","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,21]]},"assertion":[{"value":"8 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}