{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T12:47:35Z","timestamp":1771505255437,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,3,23]],"date-time":"2020-03-23T00:00:00Z","timestamp":1584921600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,23]],"date-time":"2020-03-23T00:00:00Z","timestamp":1584921600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1656951"],"award-info":[{"award-number":["1656951"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1750162"],"award-info":[{"award-number":["1750162"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000084","name":"Directorate for Engineering","doi-asserted-by":"publisher","award":["1254129"],"award-info":[{"award-number":["1254129"]}],"id":[{"id":"10.13039\/100000084","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006199","name":"Langley Research Center","doi-asserted-by":"publisher","award":["NNX12AM55A"],"award-info":[{"award-number":["NNX12AM55A"]}],"id":[{"id":"10.13039\/100006199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s10107-020-01486-1","type":"journal-article","created":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T00:12:43Z","timestamp":1585008763000},"page":"383-408","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Analysis of biased stochastic gradient descent using sequential semidefinite programs"],"prefix":"10.1007","volume":"187","author":[{"given":"Bin","family":"Hu","sequence":"first","affiliation":[]},{"given":"Peter","family":"Seiler","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5389-9361","authenticated-orcid":false,"given":"Laurent","family":"Lessard","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,23]]},"reference":[{"issue":"5","key":"1486_CR1","doi-asserted-by":"publisher","first-page":"3235","DOI":"10.1109\/TIT.2011.2182178","volume":"58","author":"A Agarwal","year":"2012","unstructured":"Agarwal, A., Bartlett, P.L., Ravikumar, P., Wainwright, M.J.: Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans. Inf. Theory 58(5), 3235\u20133249 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1486_CR2","unstructured":"Arora, S., Ge, R., Ma, T., Moitra, A.: Simple, efficient, and neural algorithms for sparse coding. In: Conference on Learning Theory, pp. 113\u2013149 (2015)"},{"key":"1486_CR3","volume-title":"Nonlinear Programming","author":"D Bertsekas","year":"2002","unstructured":"Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena scientific, Belmont (2002)","edition":"2"},{"key":"1486_CR4","doi-asserted-by":"crossref","unstructured":"Bottou, L.: Large-scale machine learning with stochastic gradient descent. In: Proceedings of COMPSTAT\u20192010, pp. 177\u2013186 (2010)","DOI":"10.1007\/978-3-7908-2604-3_16"},{"issue":"2","key":"1486_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/16M1080173","volume":"60","author":"L Bottou","year":"2018","unstructured":"Bottou, L., Curtis, F., Nocedal, J.: Optimization methods for large-scale machine learning. SIAM Rev. 60(2), 223\u2013311 (2018)","journal-title":"SIAM Rev."},{"key":"1486_CR6","first-page":"217","volume":"16","author":"L Bottou","year":"2004","unstructured":"Bottou, L., LeCun, Y.: Large scale online learning. Adv. Neural Inf. Process. Syst. 16, 217 (2004)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"3\u20134","key":"1486_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1561\/2200000050","volume":"8","author":"S Bubeck","year":"2015","unstructured":"Bubeck, S.: Convex optimization: algorithms and complexity. Found. Trends\u00ae Mach. Learn. 8(3\u20134), 231\u2013357 (2015)","journal-title":"Found. Trends\u00ae Mach. Learn."},{"key":"1486_CR8","unstructured":"Chen, Y., Candes, E.: Solving random quadratic systems of equations is nearly as easy as solving linear systems. In: Advances in Neural Information Processing Systems, pp. 739\u2013747 (2015)"},{"issue":"3","key":"1486_CR9","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/060676386","volume":"19","author":"A d\u2019Aspremont","year":"2008","unstructured":"d\u2019Aspremont, A.: Smooth optimization with approximate gradient. SIAM J. Optim. 19(3), 1171\u20131183 (2008)","journal-title":"SIAM J. Optim."},{"issue":"7","key":"1486_CR10","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1007\/s11590-016-1087-4","volume":"11","author":"E De Klerk","year":"2017","unstructured":"De Klerk, E., Glineur, F., Taylor, A.: On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optim. Lett. 11(7), 1185\u20131199 (2017)","journal-title":"Optim. Lett."},{"key":"1486_CR11","unstructured":"Defazio, A., Bach, F., Lacoste-Julien, S.: Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In: Advances in Neural Information Processing Systems (2014)"},{"key":"1486_CR12","unstructured":"Defazio, A., Domke, J., Caetano, T.: Finito: A faster, permutable incremental gradient method for big data problems. In: Proceedings of the 31st International Conference on Machine Learning, pp. 1125\u20131133 (2014)"},{"issue":"1\u20132","key":"1486_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10107-013-0677-5","volume":"146","author":"O Devolder","year":"2014","unstructured":"Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146(1\u20132), 37\u201375 (2014)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1486_CR14","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-013-0653-0","volume":"145","author":"Y Drori","year":"2014","unstructured":"Drori, Y., Teboulle, M.: Performance of first-order methods for smooth convex minimization: a novel approach. Math. Program. 145(1\u20132), 451\u2013482 (2014)","journal-title":"Math. Program."},{"key":"1486_CR15","doi-asserted-by":"crossref","unstructured":"Feyzmahdavian, H., Aytekin, A., Johansson, M.: A delayed proximal gradient method with linear convergence rate. In: 2014 IEEE International Workshop on Machine Learning for Signal Processing, pp. 1\u20136 (2014)","DOI":"10.1109\/MLSP.2014.6958872"},{"key":"1486_CR16","unstructured":"Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: Blondel, V., Boyd, S., Kimura, H. (eds.) Recent Advances in Learning and Control. Lecture Notes in Control and Information Sciences, pp. 95\u2013110. Springer (2008). http:\/\/stanford.edu\/~boyd\/graph_dcp.html"},{"key":"1486_CR17","unstructured":"Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. http:\/\/cvxr.com\/cvx (2014)"},{"key":"1486_CR18","unstructured":"Hu, B., Seiler, P., Rantzer, A.: A unified analysis of stochastic optimization methods using jump system theory and quadratic constraints. In: Proceedings of the 2017 Conference on Learning Theory, vol.\u00a065, pp. 1157\u20131189 (2017)"},{"key":"1486_CR19","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. In: Advances in Neural Information Processing Systems, pp. 315\u2013323 (2013)"},{"key":"1486_CR20","doi-asserted-by":"crossref","unstructured":"Lee, J.C., Valiant, P.: Optimizing star-convex functions. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 603\u2013614 (2016)","DOI":"10.1109\/FOCS.2016.71"},{"issue":"1","key":"1486_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/15M1009597","volume":"26","author":"L Lessard","year":"2016","unstructured":"Lessard, L., Recht, B., Packard, A.: Analysis and design of optimization algorithms via integral quadratic constraints. SIAM J. Optim. 26(1), 57\u201395 (2016)","journal-title":"SIAM J. Optim."},{"key":"1486_CR22","unstructured":"Moulines, E., Bach, F.: Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In: Advances in Neural Information Processing Systems, pp. 451\u2013459 (2011)"},{"key":"1486_CR23","doi-asserted-by":"crossref","unstructured":"Nedi\u0107, A., Bertsekas, D.: Convergence rate of incremental subgradient algorithms. In: Stochastic Optimization: Algorithms and Applications, pp. 223\u2013264 (2001)","DOI":"10.1007\/978-1-4757-6594-6_11"},{"key":"1486_CR24","unstructured":"Needell, D., Ward, R., Srebro, N.: Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. In: Advances in Neural Information Processing Systems, pp. 1017\u20131025 (2014)"},{"key":"1486_CR25","unstructured":"Nishihara, R., Lessard, L., Recht, B., Packard, A., Jordan, M.: A general analysis of the convergence of ADMM. In: Proceedings of the 32nd International Conference on Machine Learning, pp. 343\u2013352 (2015)"},{"issue":"3","key":"1486_CR26","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(3), 400\u2013407 (1951)","journal-title":"Ann. Math. Stat."},{"key":"1486_CR27","unstructured":"Roux, N., Schmidt, M., Bach, F.: A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets. In: Advances in Neural Information Processing Systems (2012)"},{"issue":"1\u20132","key":"1486_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., 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":"1486_CR29","unstructured":"Schmidt, M., Roux, N.L., Bach, F.R.: Convergence rates of inexact proximal-gradient methods for convex optimization. In: Advances in Neural Information Processing Systems, pp. 1458\u20131466 (2011)"},{"issue":"1","key":"1486_CR30","first-page":"567","volume":"14","author":"S Shalev-Shwartz","year":"2013","unstructured":"Shalev-Shwartz, S., Zhang, T.: Stochastic dual coordinate ascent methods for regularized loss. J. Mach. Learn. Res. 14(1), 567\u2013599 (2013)","journal-title":"J. Mach. Learn. Res."},{"issue":"11","key":"1486_CR31","doi-asserted-by":"publisher","first-page":"6535","DOI":"10.1109\/TIT.2016.2598574","volume":"62","author":"R Sun","year":"2016","unstructured":"Sun, R., Luo, Z.Q.: Guaranteed matrix completion via non-convex factorization. IEEE Trans. Inf. Theory 62(11), 6535\u20136579 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1486_CR32","unstructured":"Taylor, A., Bach, F.: Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions. In: Proceedings of the 2019 Conference on Learning Theory, pp. 2934\u20132992 (2019)"},{"issue":"1\u20132","key":"1486_CR33","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-016-1009-3","volume":"161","author":"A Taylor","year":"2017","unstructured":"Taylor, A., Hendrickx, J., Glineur, F.: Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Math. Program. 161(1\u20132), 307\u2013345 (2017)","journal-title":"Math. Program."},{"issue":"3","key":"1486_CR34","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1137\/16M108104X","volume":"27","author":"A Taylor","year":"2017","unstructured":"Taylor, A., Hendrickx, J.M., Glineur, F.: Exact worst-case performance of first-order methods for composite convex optimization. SIAM J. Optim. 27(3), 1283\u20131313 (2017)","journal-title":"SIAM J. Optim."},{"key":"1486_CR35","unstructured":"Taylor, A., Van\u00a0Scoy, B., Lessard, L.: Lyapunov functions for first-order methods: Tight automated convergence guarantees. In: Proceedings of the 35th International Conference on Machine Learning, pp. 4897\u20134906 (2018)"},{"key":"1486_CR36","doi-asserted-by":"crossref","unstructured":"Teo, C., Smola, A., Vishwanathan, S., Le, Q.: A scalable modular convex solver for regularized risk minimization. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 727\u2013736 (2007)","DOI":"10.1145\/1281192.1281270"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01486-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01486-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01486-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T18:50:16Z","timestamp":1618944616000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01486-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,23]]},"references-count":36,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["1486"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01486-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,23]]},"assertion":[{"value":"25 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}