{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T02:33:42Z","timestamp":1773801222518,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T00:00:00Z","timestamp":1724716800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T00:00:00Z","timestamp":1724716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-1953199"],"award-info":[{"award-number":["DMS-1953199"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-1953199"],"award-info":[{"award-number":["DMS-1953199"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-22-1-0447"],"award-info":[{"award-number":["FA9550-22-1-0447"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-22-1-0447"],"award-info":[{"award-number":["FA9550-22-1-0447"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Multidisciplinary Institute in Artificial intelligence MIAI @ Grenoble Alpes","award":["ANR-19-P3IA-0003"],"award-info":[{"award-number":["ANR-19-P3IA-0003"]}]},{"name":"Multidisciplinary Institute in Artificial intelligence MIAI @ Grenoble Alpes","award":["ANR-19-P3IA-0003"],"award-info":[{"award-number":["ANR-19-P3IA-0003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s10107-024-02138-4","type":"journal-article","created":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T13:02:36Z","timestamp":1724763756000},"page":"239-280","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Accelerated stochastic approximation with state-dependent noise"],"prefix":"10.1007","volume":"213","author":[{"given":"Sasila","family":"Ilandarideva","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anatoli","family":"Juditsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guanghui","family":"Lan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6660-0883","authenticated-orcid":false,"given":"Tianjiao","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,27]]},"reference":[{"key":"2138_CR1","unstructured":"Agarwal, A., Negahban, S., Wainwright, M.J.: Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions. In: Advances in Neural Information Processing Systems, vol. 25 (2012)"},{"key":"2138_CR2","doi-asserted-by":"crossref","unstructured":"Bickel, P.J., Ritov, Y., Tsybakov, A.B.: Simultaneous analysis of lasso and Dantzig selector (2009)","DOI":"10.1214\/08-AOS620"},{"key":"2138_CR3","unstructured":"Bietti, A., Mairal, J.: Stochastic optimization with variance reduction for infinite datasets with finite sum structure. In: Advances in Neural Information Processing Systems, vol. 30 (2017)"},{"issue":"3","key":"2138_CR4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.acha.2009.04.002","volume":"27","author":"T Blumensath","year":"2009","unstructured":"Blumensath, T., Davies, M.E.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27(3), 265\u2013274 (2009)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"6","key":"2138_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1145\/2184319.2184343","volume":"55","author":"E Candes","year":"2012","unstructured":"Candes, E., Recht, B.: Exact matrix completion via convex optimization. Commun. ACM 55(6), 111\u2013119 (2012)","journal-title":"Commun. ACM"},{"key":"2138_CR6","doi-asserted-by":"crossref","unstructured":"Candes, E., Tao, T.: The Dantzig selector: statistical estimation when p is much larger than n (2007)","DOI":"10.1214\/009053606000001523"},{"issue":"5A","key":"2138_CR7","doi-asserted-by":"publisher","first-page":"2145","DOI":"10.1214\/08-AOS653","volume":"37","author":"EJ Candes","year":"2009","unstructured":"Candes, E.J., Plan, Y.: Near-ideal model selection by $$\\ell _1$$ minimization. Ann. Stat. 37(5A), 2145\u20132177 (2009)","journal-title":"Ann. Stat."},{"issue":"11","key":"2138_CR8","doi-asserted-by":"publisher","first-page":"7235","DOI":"10.1109\/TIT.2011.2161794","volume":"57","author":"EJ Candes","year":"2011","unstructured":"Candes, E.J., Plan, Y.: A probabilistic and Ripless theory of compressed sensing. IEEE Trans. Inf. Theory 57(11), 7235\u20137254 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"2138_CR9","doi-asserted-by":"publisher","first-page":"2342","DOI":"10.1109\/TIT.2011.2111771","volume":"57","author":"EJ Candes","year":"2011","unstructured":"Candes, E.J., Plan, Y.: Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Trans. Inf. Theory 57(4), 2342\u20132359 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"8","key":"2138_CR10","first-page":"1207","volume":"59","author":"EJ Candes","year":"2006","unstructured":"Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Appl. Math. J. Issued Courant Inst. Math. Sci. 59(8), 1207\u20131223 (2006)","journal-title":"Commun. Appl. Math. J. Issued Courant Inst. Math. Sci."},{"key":"2138_CR11","unstructured":"Cotter, A., Shamir, O., Srebro, N., Sridharan, K.: Better mini-batch algorithms via accelerated gradient methods. In: Advances in Neural Information Processing Systems, vol. 24 (2011)"},{"key":"2138_CR12","doi-asserted-by":"crossref","unstructured":"Fazel, M., Candes, E., Recht, B., Parrilo, P.: Compressed sensing and robust recovery of low rank matrices. In: 2008 42nd Asilomar Conference on Signals, Systems and Computers, pp. 1043\u20131047. IEEE (2008)","DOI":"10.1109\/ACSSC.2008.5074571"},{"key":"2138_CR13","unstructured":"Gaillard, P., Wintenberger, O.: Sparse accelerated exponential weights. In: Artificial Intelligence and Statistics, pp. 75\u201382. PMLR (2017)"},{"issue":"4","key":"2138_CR14","doi-asserted-by":"publisher","first-page":"1469","DOI":"10.1137\/110848864","volume":"22","author":"S Ghadimi","year":"2012","unstructured":"Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: a generic algorithmic framework. SIAM J. Optim. 22(4), 1469\u20131492 (2012)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"2138_CR15","doi-asserted-by":"publisher","first-page":"2061","DOI":"10.1137\/110848876","volume":"23","author":"S Ghadimi","year":"2013","unstructured":"Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms. SIAM J. Optim. 23(4), 2061\u20132089 (2013)","journal-title":"SIAM J. Optim."},{"key":"2138_CR16","unstructured":"Gower, R., Sebbouh, O., Loizou, N.: SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In: International Conference on Artificial Intelligence and Statistics, pp. 1315\u20131323. PMLR (2021)"},{"key":"2138_CR17","unstructured":"Gower, R.M., Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E., Richt\u00e1rik, P.: SGD: General analysis and improved rates. In: International Conference on Machine Learning, pp. 5200\u20135209. PMLR (2019)"},{"key":"2138_CR18","unstructured":"Ilandarideva, S., Bekri, Y., Iouditski, A., Perchet, V.: Stochastic mirror descent for large-scale sparse recovery. In: International Conference on Artificial Intelligence and Statistics, pp. 5931\u20135957. PMLR (2023)"},{"key":"2138_CR19","unstructured":"Jain, P., Tewari, A., Kar, P.: On iterative hard thresholding methods for high-dimensional m-estimation. In: Advances in Neural Information Processing Systems, vol. 27 (2014)"},{"issue":"2","key":"2138_CR20","first-page":"851","volume":"12","author":"A Juditsky","year":"2023","unstructured":"Juditsky, A., Kulunchakov, A., Tsyntseus, H.: Sparse recovery by reduced variance stochastic approximation. Inf. Inference J. IMA 12(2), 851\u2013896 (2023)","journal-title":"Inf. Inference J. IMA"},{"issue":"12","key":"2138_CR21","doi-asserted-by":"publisher","first-page":"7818","DOI":"10.1109\/TIT.2011.2162569","volume":"57","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A.: Accuracy guarantees for $$\\ell _1$$-recovery. IEEE Trans. Inf. Theory 57(12), 7818\u20137839 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"9","key":"2138_CR22","first-page":"121","volume":"30","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A., et al.: First order methods for nonsmooth convex large-scale optimization, I: general purpose methods. Optim. Mach. Learn. 30(9), 121\u2013148 (2011)","journal-title":"Optim. Mach. Learn."},{"issue":"1","key":"2138_CR23","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1287\/10-SSY010","volume":"4","author":"A Juditsky","year":"2014","unstructured":"Juditsky, A., Nesterov, Y.: Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stochast. Syst. 4(1), 44\u201380 (2014)","journal-title":"Stochast. Syst."},{"key":"2138_CR24","unstructured":"Khaled, A., Richt\u00e1rik, P.: Better theory for SGD in the nonconvex world. Trans. Mach. Learn. Res. (2022)"},{"issue":"3","key":"2138_CR25","doi-asserted-by":"publisher","first-page":"2041","DOI":"10.1137\/20M1381678","volume":"32","author":"G Kotsalis","year":"2022","unstructured":"Kotsalis, G., Lan, G., Li, T.: Simple and optimal methods for stochastic variational inequalities, I: Operator extrapolation. SIAM J. Optim. 32(3), 2041\u20132073 (2022)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2138_CR26","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1137\/20M1381691","volume":"32","author":"G Kotsalis","year":"2022","unstructured":"Kotsalis, G., Lan, G., Li, T.: Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning. SIAM J. Optim. 32(2), 1120\u20131155 (2022)","journal-title":"SIAM J. Optim."},{"key":"2138_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511550683","volume-title":"Multivariate t-Distributions and Their Applications","author":"S Kotz","year":"2004","unstructured":"Kotz, S., Nadarajah, S.: Multivariate t-Distributions and Their Applications. Cambridge University Press, Cambridge (2004)"},{"issue":"1\u20132","key":"2138_CR28","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-010-0434-y","volume":"133","author":"G Lan","year":"2012","unstructured":"Lan, G.: An optimal method for stochastic composite optimization. Math. Program. 133(1\u20132), 365\u2013397 (2012)","journal-title":"Math. Program."},{"key":"2138_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-Order and Stochastic Optimization Methods for Machine Learning","author":"G Lan","year":"2020","unstructured":"Lan, G.: First-Order and Stochastic Optimization Methods for Machine Learning, vol. 1. Springer, Berlin (2020)"},{"key":"2138_CR30","unstructured":"Lan, G., Zhou, Y.: An optimal randomized incremental gradient method. Math. Program. (2015). arXiv:1507.02000"},{"issue":"4","key":"2138_CR31","doi-asserted-by":"publisher","first-page":"2753","DOI":"10.1137\/17M1157891","volume":"28","author":"G Lan","year":"2018","unstructured":"Lan, G., Zhou, Y.: Random gradient extrapolation for distributed and stochastic optimization. SIAM J. Optim. 28(4), 2753\u20132782 (2018)","journal-title":"SIAM J. Optim."},{"key":"2138_CR32","unstructured":"Li, T., Lan, G., Pananjady, A.: Accelerated and instance-optimal policy evaluation with linear function approximation. arXiv preprint arXiv:2112.13109 (2021)"},{"key":"2138_CR33","unstructured":"Li, T., Wu, F., Lan, G.: Stochastic first-order methods for average-reward Markov decision processes. arXiv preprint arXiv:2205.05800 (2022)"},{"key":"2138_CR34","unstructured":"Liu, C., Belkin, M.: Mass: an accelerated stochastic method for over-parametrized learning. arXiv preprint arXiv:1810.13395 (2018)"},{"issue":"4","key":"2138_CR35","first-page":"899","volume":"9","author":"H Liu","year":"2020","unstructured":"Liu, H., Foygel Barber, R.: Between hard and soft thresholding: optimal iterative thresholding algorithms. Inf. Inference J. IMA 9(4), 899\u2013933 (2020)","journal-title":"Inf. Inference J. IMA"},{"issue":"4","key":"2138_CR36","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1137\/070704277","volume":"19","author":"A Nemirovski","year":"2009","unstructured":"Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4), 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"key":"2138_CR37","first-page":"1979","volume":"384","author":"A Nemirovski","year":"1979","unstructured":"Nemirovski, A., Yudin, D.: Complexity of problems and effectiveness of methods of optimization (Russian book). Moscow, Izdatel\u2019stvo Nauka 384, 1979 (1979)","journal-title":"Moscow, Izdatel\u2019stvo Nauka"},{"key":"2138_CR38","volume-title":"Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics, XV","author":"AS Nemirovski","year":"1983","unstructured":"Nemirovski, A.S., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics, XV. Wiley, New York (1983)"},{"key":"2138_CR39","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0041-5553(85)90100-4","volume":"25","author":"A Nemirovskii","year":"1985","unstructured":"Nemirovskii, A., Nesterov, Y.: Optimal methods of smooth convex minimization. USSR Comput. Math. Math. Phys. 25, 21\u201330 (1985)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"2138_CR40","first-page":"76","volume":"1","author":"A Nemirovskii","year":"1983","unstructured":"Nemirovskii, A., Yudin, D.: Information-based complexity of mathematical programming. Eng. Cybernet. 1, 76\u2013100 (1983)","journal-title":"Eng. Cybernet."},{"key":"2138_CR41","first-page":"543","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence $$O(1\/k^2)$$. Doklady an USSR 269, 543\u2013547 (1983)","journal-title":"Doklady an USSR"},{"key":"2138_CR42","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1017\/S096249291300007X","volume":"22","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y., Nemirovski, A.: On first-order algorithms for $$\\ell _1$$\/nuclear norm minimization. Acta Numerica 22, 509\u2013575 (2013)","journal-title":"Acta Numerica"},{"issue":"98\u2013107","key":"2138_CR43","first-page":"2","volume":"7","author":"BT Polyak","year":"1990","unstructured":"Polyak, B.T.: New stochastic approximation type procedures. Automat. i Telemekh 7(98\u2013107), 2 (1990)","journal-title":"Automat. i Telemekh"},{"issue":"4","key":"2138_CR44","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0330046","volume":"30","author":"BT Polyak","year":"1992","unstructured":"Polyak, B.T., Juditsky, A.B.: Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30(4), 838\u2013855 (1992)","journal-title":"SIAM J. Control Optim."},{"key":"2138_CR45","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., Tewari, A.: Stochastic methods for $$\\ell _1$$ regularized loss minimization. In: Proceedings of the 26th Annual International Conference on Machine Learning, pp. 929\u2013936 (2009)","DOI":"10.1145\/1553374.1553493"},{"key":"2138_CR46","unstructured":"Srebro, N., Sridharan, K., Tewari, A.: Smoothness, low noise and fast rates. In: Advances in Neural Information Processing Systems, vol. 23 (2010)"},{"issue":"5","key":"2138_CR47","first-page":"2302","volume":"39","author":"A Tsybakov","year":"2011","unstructured":"Tsybakov, A., Koltchinskii, V., Lounici, K.: Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. Ann. Stat. 39(5), 2302\u20132329 (2011)","journal-title":"Ann. Stat."},{"key":"2138_CR48","first-page":"7333","volume":"34","author":"BE Woodworth","year":"2021","unstructured":"Woodworth, B.E., Srebro, N.: An even more optimal stochastic optimization algorithm: minibatching and interpolation learning. Adv. Neural Inf. Process. Syst. 34, 7333\u20137345 (2021)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"2138_CR49","first-page":"550","volume":"3","author":"D Yudin","year":"1977","unstructured":"Yudin, D., Nemirovski, A.: Computational complexity of strictly convex programming. Eknomika i Matematicheskie Metody 3, 550\u2013569 (1977)","journal-title":"Eknomika i Matematicheskie Metody"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02138-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02138-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02138-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T21:05:36Z","timestamp":1757106336000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02138-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,27]]},"references-count":49,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["2138"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02138-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,27]]},"assertion":[{"value":"13 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no other Conflict of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}