{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T22:57:06Z","timestamp":1769295426696,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T00:00:00Z","timestamp":1769126400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T00:00:00Z","timestamp":1769126400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We present Q-SASS, a quasi-Newton method for unconstrained stochastic optimization that does not rely on common random numbers. Most existing quasi-Newton approaches leverage common random numbers to construct second-order updates. However, motivated by challenges in variational quantum algorithms\u2014where such coordination is not possible\u2014we consider the setting in which function values and gradients are accessible only through noisy probabilistic zeroth- and first-order oracles, and no common random numbers can be exploited. We derive high-probability tail bounds on the iteration complexity of our algorithm for nonconvex, convex, and strongly convex (more generally, those satisfying the PL condition) objective functions. Finally, we demonstrate the empirical benefits of our quasi-Newton updating scheme on both synthetic and quantum chemistry problems.<\/jats:p>","DOI":"10.1007\/s10957-025-02914-y","type":"journal-article","created":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T12:24:50Z","timestamp":1769171090000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Stochastic Quasi-Newton Method in the Absence of Common Random Numbers"],"prefix":"10.1007","volume":"208","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2023-0837","authenticated-orcid":false,"given":"Matt","family":"Menickelly","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6099-2772","authenticated-orcid":false,"given":"Stefan M.","family":"Wild","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8511-9649","authenticated-orcid":false,"given":"Miaolan","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,23]]},"reference":[{"key":"2914_CR1","doi-asserted-by":"publisher","unstructured":"Anis, M.S., Abraham, H., AduOffei, Agarwal, R., Agliardi, G., Aharoni, M., Akhalwaya, I.Y., Aleksandrowicz, G., Alexander, T., Amy, M., Anagolum, S., Arbel, E., Asfaw, A., Athalye, A., Avkhadiev, A., et\u00a0al.: Qiskit: An open-source framework for quantum computing (2021). https:\/\/doi.org\/10.5281\/zenodo.2573505","DOI":"10.5281\/zenodo.2573505"},{"key":"2914_CR2","unstructured":"Bach, F., Perchet, V.: Highly-smooth zero-th order online optimization. In: Conference on Learning Theory, pp. 257\u2013283. PMLR (2016). http:\/\/proceedings.mlr.press\/v49\/bach16.html"},{"issue":"2","key":"2914_CR3","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s10208-021-09513-z","volume":"22","author":"AS Berahas","year":"2022","unstructured":"Berahas, A.S., Cao, L., Choromanski, K., Scheinberg, K.: A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Found. Comput. Math. 22(2), 507\u2013560 (2022). https:\/\/doi.org\/10.1007\/s10208-021-09513-z","journal-title":"Found. Comput. Math."},{"issue":"2","key":"2914_CR4","doi-asserted-by":"publisher","first-page":"1489","DOI":"10.1137\/19M1291832","volume":"31","author":"AS Berahas","year":"2021","unstructured":"Berahas, A.S., Cao, L., Scheinberg, K.: Global convergence rate analysis of a generic line search algorithm with noise. SIAM J. Optim. 31(2), 1489\u20131518 (2021). https:\/\/doi.org\/10.1137\/19M1291832","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2914_CR5","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/23m1549006","volume":"35","author":"AS Berahas","year":"2025","unstructured":"Berahas, A.S., Xie, M., Zhou, B.: A sequential quadratic programming method with high-probability complexity bounds for nonlinear equality-constrained stochastic optimization. SIAM J. Optim. 35(1), 240\u2013269 (2025). https:\/\/doi.org\/10.1137\/23m1549006","journal-title":"SIAM J. Optim."},{"key":"2914_CR6","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s12532-023-00233-9","volume":"15","author":"R Bollapragada","year":"2023","unstructured":"Bollapragada, R., Wild, S.M.: Adaptive sampling quasi-Newton methods for zeroth-order stochastic optimization. Math. Program. Comput. 15, 327\u2013364 (2023). https:\/\/doi.org\/10.1007\/s12532-023-00233-9","journal-title":"Math. Program. Comput."},{"issue":"59","key":"2914_CR7","first-page":"1737","volume":"10","author":"A Bordes","year":"2009","unstructured":"Bordes, A., Bottou, L., Gallinari, P.: SGD-QN: Careful quasi-Newton stochastic gradient descent. J. Mach. Learn. Res. 10(59), 1737\u20131754 (2009)","journal-title":"J. Mach. Learn. Res."},{"issue":"110","key":"2914_CR8","doi-asserted-by":"publisher","first-page":"365","DOI":"10.2307\/2004483","volume":"24","author":"CG Broyden","year":"1970","unstructured":"Broyden, C.G.: The convergence of single-rank quasi-Newton methods. Math. Comput. 24(110), 365\u2013382 (1970). https:\/\/doi.org\/10.2307\/2004483","journal-title":"Math. Comput."},{"issue":"1","key":"2914_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s10589-019-00112-x","volume":"74","author":"J Brust","year":"2019","unstructured":"Brust, J., Burdakov, O., Erway, J.B., Marcia, R.F.: A dense initialization for limited-memory quasi-Newton methods. Comput. Optim. Appl. 74(1), 121\u2013142 (2019). https:\/\/doi.org\/10.1007\/s10589-019-00112-x","journal-title":"Comput. Optim. Appl."},{"key":"2914_CR10","doi-asserted-by":"crossref","unstructured":"Cao, L., Berahas, A.S., Scheinberg, K.: First-and second-order high probability complexity bounds for trust-region methods with noisy oracles. arXiv preprint arXiv:2205.03667 (2022)","DOI":"10.1007\/s10107-023-01999-5"},{"issue":"3","key":"2914_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3338517","volume":"45","author":"C Cartis","year":"2019","unstructured":"Cartis, C., Fiala, J., Marteau, B., Roberts, L.: Improving the flexibility and robustness of model-based derivative-free optimization solvers. ACM Trans. Math. Softw. 45(3), 1\u201341 (2019). https:\/\/doi.org\/10.1145\/3338517","journal-title":"ACM Trans. Math. Softw."},{"key":"2914_CR12","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1038\/s42254-021-00348-9","volume":"3","author":"M Cerezo","year":"2021","unstructured":"Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S.C., Endo, S., Fujii, K., McClean, J.R., Mitarai, K., Yuan, X., Cincio, L., et al.: Variational quantum algorithms. Nat. Rev. Phys. 3, 625\u2013644 (2021). https:\/\/doi.org\/10.1038\/s42254-021-00348-9","journal-title":"Nat. Rev. Phys."},{"issue":"2","key":"2914_CR13","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2002). https:\/\/doi.org\/10.1007\/s101070100263","journal-title":"Math. Program."},{"issue":"5","key":"2914_CR14","doi-asserted-by":"publisher","first-page":"2788","DOI":"10.1109\/TIT.2015.2409256","volume":"61","author":"JC Duchi","year":"2015","unstructured":"Duchi, J.C., Jordan, M.I., Wainwright, M.J., Wibisono, A.: Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Trans. Inf. Theory 61(5), 2788\u20132806 (2015). https:\/\/doi.org\/10.1109\/TIT.2015.2409256","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2914_CR15","doi-asserted-by":"publisher","unstructured":"Flaxman, A.D., Kalai, A.T., McMahan, H.B.: Online convex optimization in the bandit setting: gradient descent without a gradient. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 385\u2013394. Society for Industrial and Applied Mathematics (2005). https:\/\/doi.org\/10.5555\/1070432.1070486","DOI":"10.5555\/1070432.1070486"},{"issue":"3","key":"2914_CR16","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1093\/comjnl\/13.3.317","volume":"13","author":"R Fletcher","year":"1970","unstructured":"Fletcher, R.: A new approach to variable metric algorithms. Comput. J. 13(3), 317\u2013322 (1970)","journal-title":"Comput. J."},{"issue":"109","key":"2914_CR17","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1090\/s0025-5718-1970-0258249-6","volume":"24","author":"D Goldfarb","year":"1970","unstructured":"Goldfarb, D.: A family of variable-metric methods derived by variational means. Math. Comput. 24(109), 23\u201326 (1970). https:\/\/doi.org\/10.1090\/s0025-5718-1970-0258249-6","journal-title":"Math. Comput."},{"issue":"3","key":"2914_CR18","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10589-014-9687-3","volume":"60","author":"NI Gould","year":"2015","unstructured":"Gould, N.I., Orban, D., Toint, P.L.: CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. 60(3), 545\u2013557 (2015). https:\/\/doi.org\/10.1007\/s10589-014-9687-3","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"2914_CR19","doi-asserted-by":"publisher","first-page":"1579","DOI":"10.1093\/imanum\/drx043","volume":"38","author":"S Gratton","year":"2018","unstructured":"Gratton, S., Royer, C.W., Vicente, L.N., Zhang, Z.: Complexity and global rates of trust-region methods based on probabilistic models. IMA J. Numer. Anal. 38(3), 1579\u20131597 (2018). https:\/\/doi.org\/10.1093\/imanum\/drx043","journal-title":"IMA J. Numer. Anal."},{"key":"2914_CR20","doi-asserted-by":"publisher","DOI":"10.1002\/9781119019572","volume-title":"Molecular Electronic-Structure Theory","author":"T Helgaker","year":"2014","unstructured":"Helgaker, T., Jorgensen, P., Olsen, J.: Molecular Electronic-Structure Theory. John Wiley & Sons, Hoboken (2014). https:\/\/doi.org\/10.1002\/9781119019572"},{"issue":"3","key":"2914_CR21","doi-asserted-by":"publisher","first-page":"2411","DOI":"10.1137\/22M1512764","volume":"34","author":"B Jin","year":"2024","unstructured":"Jin, B., Scheinberg, K., Xie, M.: High probability complexity bounds for adaptive step search based on stochastic oracles. SIAM J. Optim. 34(3), 2411\u20132439 (2024)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"2914_CR22","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1007\/s10107-024-02078-z","volume":"209","author":"B Jin","year":"2025","unstructured":"Jin, B., Scheinberg, K., Xie, M.: Sample complexity analysis for adaptive optimization algorithms with stochastic oracles. Math. Program. 209(1\u20132), 651\u2013679 (2025). https:\/\/doi.org\/10.1007\/s10107-024-02078-z","journal-title":"Math. Program."},{"key":"2914_CR23","doi-asserted-by":"publisher","unstructured":"Menickelly, M., Ha, Y., Otten, M.: Latency considerations for stochastic optimizers in variational quantum algorithms. Quantum 7(949) (2023). https:\/\/doi.org\/10.22331\/q-2023-03-16-949","DOI":"10.22331\/q-2023-03-16-949"},{"issue":"2","key":"2914_CR24","doi-asserted-by":"publisher","first-page":"1670","DOI":"10.1137\/17M1122943","volume":"28","author":"A Mokhtari","year":"2018","unstructured":"Mokhtari, A., Eisen, M., Ribeiro, A.: IQN: An incremental quasi-Newton method with local superlinear convergence rate. SIAM J. Optim. 28(2), 1670\u20131698 (2018). https:\/\/doi.org\/10.1137\/17M1122943","journal-title":"SIAM J. Optim."},{"issue":"23","key":"2914_CR25","doi-asserted-by":"publisher","first-page":"6089","DOI":"10.1109\/TSP.2014.2357775","volume":"62","author":"A Mokhtari","year":"2014","unstructured":"Mokhtari, A., Ribeiro, A.: RES: Regularized stochastic BFGS algorithm. IEEE Trans. Signal Process. 62(23), 6089\u20136104 (2014). https:\/\/doi.org\/10.1109\/TSP.2014.2357775","journal-title":"IEEE Trans. Signal Process."},{"issue":"11","key":"2914_CR26","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1109\/JPROC.2020.3023660","volume":"108","author":"A Mokhtari","year":"2020","unstructured":"Mokhtari, A., Ribeiro, A.: Stochastic quasi-Newton methods. Proc. IEEE 108(11), 1906\u20131922 (2020). https:\/\/doi.org\/10.1109\/JPROC.2020.3023660","journal-title":"Proc. IEEE"},{"issue":"1","key":"2914_CR27","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/080724083","volume":"20","author":"JJ Mor\u00e9","year":"2009","unstructured":"Mor\u00e9, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20(1), 172\u2013191 (2009). https:\/\/doi.org\/10.1137\/080724083","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2914_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/100786125","volume":"38","author":"JJ Mor\u00e9","year":"2012","unstructured":"Mor\u00e9, J.J., Wild, S.M.: Estimating derivatives of noisy simulations. ACM Trans. Math. Softw. 38(3), 1\u201321 (2012). https:\/\/doi.org\/10.1137\/100786125","journal-title":"ACM Trans. Math. Softw."},{"key":"2914_CR29","unstructured":"Moritz, P., Nishihara, R., Jordan, M.: A linearly-convergent stochastic L-BFGS algorithm. In: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pp. 249\u2013258 (2016). https:\/\/proceedings.mlr.press\/v51\/moritz16.html"},{"key":"2914_CR30","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.: Numerical Optimization, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"issue":"4","key":"2914_CR31","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1016\/0041-5553(63)90382-3","volume":"3","author":"BT Polyak","year":"1963","unstructured":"Polyak, B.T.: Gradient methods for the minimisation of functionals. USSR Comput. Math. Math. Phys. 3(4), 864\u2013878 (1963). https:\/\/doi.org\/10.1016\/0041-5553(63)90382-3","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"1","key":"2914_CR32","doi-asserted-by":"publisher","first-page":"5396","DOI":"10.1038\/s41467-020-19074-4","volume":"11","author":"T Proctor","year":"2020","unstructured":"Proctor, T., Revelle, M., Nielsen, E., Rudinger, K., Lobser, D., Maunz, P., Blume-Kohout, R., Young, K.: Detecting and tracking drift in quantum information processors. Nat. Commun. 11(1), 5396 (2020). https:\/\/doi.org\/10.1038\/s41467-020-19074-4","journal-title":"Nat. Commun."},{"key":"2914_CR33","doi-asserted-by":"publisher","unstructured":"Scheinberg, K., Xie, M.: Stochastic adaptive regularization method with cubics: A high probability complexity bound. In: Proceedings of the 2023 Winter Simulation Conference, pp. 3520\u20133531. IEEE (2024). https:\/\/doi.org\/10.5555\/3643142.3643436","DOI":"10.5555\/3643142.3643436"},{"issue":"3","key":"2914_CR34","doi-asserted-by":"publisher","first-page":"032,331","DOI":"10.1103\/PhysRevA.99.032331","volume":"99","author":"M Schuld","year":"2019","unstructured":"Schuld, M., Bergholm, V., Gogolin, C., Izaac, J., Killoran, N.: Evaluating analytic gradients on quantum hardware. Phys. Rev. A 99(3), 032,331 (2019). https:\/\/doi.org\/10.1103\/PhysRevA.99.032331","journal-title":"Phys. Rev. A"},{"issue":"111","key":"2914_CR35","doi-asserted-by":"publisher","first-page":"647","DOI":"10.2307\/2004840","volume":"24","author":"DF Shanno","year":"1970","unstructured":"Shanno, D.F.: Conditioning of quasi-Newton methods for function minimization. Math. Comput. 24(111), 647\u2013656 (1970). https:\/\/doi.org\/10.2307\/2004840","journal-title":"Math. Comput."},{"issue":"4","key":"2914_CR36","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1145\/279232.279236","volume":"23","author":"C Zhu","year":"1997","unstructured":"Zhu, C., Byrd, R.H., Lu, P., Nocedal, J.: Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Trans. Math. Softw. 23(4), 550\u2013560 (1997). https:\/\/doi.org\/10.1145\/279232.279236","journal-title":"ACM Trans. Math. Softw."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-025-02914-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-025-02914-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-025-02914-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T01:05:37Z","timestamp":1769216737000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-025-02914-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,23]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["2914"],"URL":"https:\/\/doi.org\/10.1007\/s10957-025-02914-y","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,23]]},"assertion":[{"value":"30 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"84"}}