{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T23:36:37Z","timestamp":1759448197362,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","license":[{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS Grants-in-Aid for Scientific Research","award":["20K22301 and 21K03347"],"award-info":[{"award-number":["20K22301 and 21K03347"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>Adaptive Monte Carlo variance reduction is an effective framework for running a Monte Carlo simulation along with a parameter search algorithm for variance reduction, whereas an initialization step is required for preparing problem parameters in some instances. In spite of the effectiveness of adaptive variance reduction in various fields of application, the length of the preliminary phase has often been left unspecified for the user to determine on a case-by-case basis, much like in typical sequential frameworks. This uncertain element may possibly be even fatal in realistic finite-budget situations, since the pilot run may take most of the budget, or possibly use up all of it. To unnecessitate such an ad hoc initialization step, we develop a batching procedure in adaptive variance reduction, and provide an implementable formula of the learning rate in the parameter search which minimizes an upper bound of the theoretical variance of the empirical batch mean. We analyze decay rates of the minimized upper bound towards the minimal estimator variance with respect to the predetermined computing budget, and provide convergence results as the computing budget increases progressively when the batch size is fixed. Numerical examples are provided to support theoretical findings and illustrate the effectiveness of the proposed batching procedure.<\/jats:p>","DOI":"10.1145\/3573386","type":"journal-article","created":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T12:36:58Z","timestamp":1669898218000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Batching Adaptive Variance Reduction"],"prefix":"10.1145","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6603-4914","authenticated-orcid":false,"given":"Chenxiao","family":"Song","sequence":"first","affiliation":[{"name":"The University of Sydney, Camperdown, NSW, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3845-015X","authenticated-orcid":false,"given":"Reiichiro","family":"Kawai","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Meguro-ku, Tokyo, Japan"}]}],"member":"320","published-online":{"date-parts":[[2023,2,28]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/974734.974738"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1515\/156939604323091180"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-4730(99)00014-4"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6911(97)90015-3"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/2909481.2909489"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2133390.2133394"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.2.494"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021068"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.strusafe.2007.10.002"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.probengmech.2010.11.002"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200020593"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2015.11.004"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1515\/mcma.2007.010"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11009-007-9043-5"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/070680564"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1734222.1734225"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1047192"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2017.01.029"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1173472"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2019.123608"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1070.0251"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/b97441"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1515\/mcma.2011.002"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1214\/09-AAP650"},{"key":"e_1_3_2_26_2","article-title":"Accelerated almost-sure convergence rates for nonconvex stochastic gradient descent using stochastic learning rates","author":"Mamalis Theodoros","year":"2021","unstructured":"Theodoros Mamalis, Dusan Stipanovic, and Petros Voulgaris. 2021. Accelerated almost-sure convergence rates for nonconvex stochastic gradient descent using stochastic learning rates. arXiv:2110.12634 (2021).","journal-title":"arXiv:2110.12634"},{"key":"e_1_3_2_27_2","article-title":"Stochastic learning rate optimization in the stochastic approximation and online learning settings","author":"Mamalis Theodoros","year":"2021","unstructured":"Theodoros Mamalis, Dusan Stipanovic, and Petros Voulgaris. 2021. Stochastic learning rate optimization in the stochastic approximation and online learning settings. arXiv:2110.10710 (2021).","journal-title":"arXiv:2110.10710"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2558328"},{"key":"e_1_3_2_29_2","first-page":"543","article-title":"A method for unconstrained convex minimization problem with the rate of convergence  \\(O(1\/k^2)\\)","volume":"269","author":"Nesterov Yurii","year":"1983","unstructured":"Yurii Nesterov. 1983. A method for unconstrained convex minimization problem with the rate of convergence \\(O(1\/k^2)\\) . Doklady ANSSSR (Translated as Soviet.Math.Docl.) 269 (1983), 543\u2013547.","journal-title":"Doklady ANSSSR (Translated as Soviet.Math.Docl.)"},{"key":"e_1_3_2_30_2","first-page":"195","volume-title":"Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research)","volume":"51","author":"Nitanda Atsushi","year":"2016","unstructured":"Atsushi Nitanda. 2016. Accelerated stochastic gradient descent for minimizing finite sums. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research), Arthur Gretton and Christian C. Robert (Eds.), Vol. 51. PMLR, Cadiz, Spain, 195\u2013203. http:\/\/proceedings.mlr.press\/v51\/nitanda16.html."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1080\/00949659208810398"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.21938"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0330046"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(98)00116-6"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/982639.982643"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.30.3.556"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718751"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1080\/24725854.2022.2076178"},{"key":"e_1_3_2_39_2","article-title":"WNGrad: Learn the learning rate in gradient descent","author":"Wu Xiaoxia","year":"2018","unstructured":"Xiaoxia Wu, Rachel Ward, and Leon Bottou. 2018. WNGrad: Learn the learning rate in gradient descent. arXiv:1803.02865 (2018).","journal-title":"arXiv:1803.02865"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3573386","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3573386","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:37Z","timestamp":1750178257000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3573386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,28]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3573386"],"URL":"https:\/\/doi.org\/10.1145\/3573386","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2023,2,28]]},"assertion":[{"value":"2021-12-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-22","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}