{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:27:56Z","timestamp":1760171276650,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T00:00:00Z","timestamp":1661385600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T00:00:00Z","timestamp":1661385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1231216"],"award-info":[{"award-number":["CCF-1231216"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DFG - SFB1294"},{"name":"DFG - MATH"},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["SLING 819789"],"award-info":[{"award-number":["SLING 819789"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006211","name":"Humboldt-Universit\u00e4t zu Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006211","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Optimization in machine learning typically deals with the minimization of empirical objectives defined by training data. The ultimate goal of learning, however, is to minimize the error on future data (test error), for which the training data provides only partial information. In this view, the optimization problems that are practically feasible are based on inexact quantities that are stochastic in nature. In this paper, we show how probabilistic results, specifically gradient concentration, can be combined with results from inexact optimization to derive sharp test error guarantees. By considering unconstrained objectives, we highlight the implicit regularization properties of optimization for learning.<\/jats:p>","DOI":"10.1007\/s10589-022-00408-5","type":"journal-article","created":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T15:03:13Z","timestamp":1661439793000},"page":"265-294","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["From inexact optimization to learning via gradient concentration"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3135-8174","authenticated-orcid":false,"given":"Bernhard","family":"Stankewitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicole","family":"M\u00fccke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lorenzo","family":"Rosasco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,25]]},"reference":[{"key":"408_CR1","volume-title":"Optimization for Machine Learning. Neural Information Processing","author":"S Sra","year":"2011","unstructured":"Sra, S., Nowozin, S., Wright, S.J.: Optimization for Machine Learning. Neural Information Processing. The MIT Press, Cambridge (2011)"},{"key":"408_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York (2014)"},{"key":"408_CR3","unstructured":"Gunasekar, S., Lee, J., Soudry, D., Srebro, N.: Characterizing Implicit Bias in Terms of Optimization Geometry. In: International Conference on Machine Learning, pp. 1832\u20131841. PMLR (2018)"},{"key":"408_CR4","unstructured":"Neyshabur, B.: Implicit Regularization in Deep Learning. arXiv:1709.01953 [stat.ML] (2017)"},{"key":"408_CR5","unstructured":"Rosasco, L., Villa, S.: Learning with incremental iterative regularization. In: Advances in Neural Information Processing Systems, vol. 28. Curran Associates, Inc., Redhook, NY (2015)"},{"issue":"10","key":"408_CR6","doi-asserted-by":"publisher","first-page":"6685","DOI":"10.1109\/TIT.2019.2927563","volume":"65","author":"F Yang","year":"2019","unstructured":"Yang, F., Wei, Y., Wainwright, M.J.: Early stopping for kernel boosting algorithms: a general analysis with localized complexities. IEEE Trans. Inf. Theory 65(10), 6685\u20136703 (2019)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"408_CR7","doi-asserted-by":"publisher","first-page":"3204","DOI":"10.1214\/18-EJS1482","volume":"12","author":"G Blanchard","year":"2018","unstructured":"Blanchard, G., Hoffmann, M., Rei\u00df, M.: Early stopping for statistical inverse problems via truncated SVD estimation. Electron. J. Stat. 12(2), 3204\u20133231 (2018)","journal-title":"Electron. J. Stat."},{"issue":"76","key":"408_CR8","first-page":"1","volume":"22","author":"A Celisse","year":"2021","unstructured":"Celisse, A., Wahl, M.: Analyzing the discrepancy principle for kernelized spectral filter learning algorithms. J. Mach. Learn. Res. 22(76), 1\u201359 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"408_CR9","doi-asserted-by":"publisher","first-page":"615","DOI":"10.2307\/2372313","volume":"73","author":"L Landweber","year":"1951","unstructured":"Landweber, L.: An iteration formula for fredholm integral equations of the first kind. Am J Math 73, 615\u2013624 (1951)","journal-title":"Am J Math"},{"key":"408_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-1740-8","volume-title":"Regularization of Inverse Problems. Mathematics and its Applications","author":"H Engl","year":"1996","unstructured":"Engl, H., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Mathematics and its Applications, vol. 375. Kluwer Academic Publishers, Dordrecht (1996)"},{"key":"408_CR11","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00365-006-0663-2","volume":"26","author":"Y Yao","year":"2007","unstructured":"Yao, Y., Caponetto, A., Rosasco, L.: On early stopping in gradient descent learning. Constr. Approx. 26, 289\u2013315 (2007)","journal-title":"Constr. Approx."},{"key":"408_CR12","first-page":"335","volume":"15","author":"G Raskutti","year":"2014","unstructured":"Raskutti, G., Yu, B., Wainwright, M.J.: Early stopping and non-parametric regression: an optimal data-dependent stopping rule. J. Mach. Learn. Res. 15, 335\u2013366 (2014)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"408_CR13","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.jco.2006.07.001","volume":"23","author":"F Bauer","year":"2007","unstructured":"Bauer, F., Pereverzev, S., Rosasco, L.: On regularization algorithms in learning theory. J. Complex. 23(1), 52\u201372 (2007)","journal-title":"J. Complex."},{"key":"408_CR14","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1007\/s10208-017-9359-7","volume":"18","author":"G Blanchard","year":"2018","unstructured":"Blanchard, G., M\u00fccke, N.: Optimal rates for regularization of statistical inverse learning problems. Found. Comput. Math. 18, 971\u20131013 (2018)","journal-title":"Found. Comput. Math."},{"issue":"1","key":"408_CR15","first-page":"3520","volume":"18","author":"A Dieuleveut","year":"2017","unstructured":"Dieuleveut, A., Flammarion, N., Bach, F.: Harder, better, faster, stronger convergence rates for least-squares regression. J. Mach. Learn. Res. 18(1), 3520\u20133570 (2017)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"408_CR16","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1214\/15-AOS1391","volume":"44","author":"A Dieuleveut","year":"2016","unstructured":"Dieuleveut, A., Bach, F.: Nonparametric stochastic approximation with large step-sizes. Ann. Stat. 44(4), 1363\u20131399 (2016)","journal-title":"Ann. Stat."},{"key":"408_CR17","unstructured":"M\u00fccke, N., Neu, G., Rosasco, L.: Beating SGD Saturation with Tail-averaging and Minibatching. In: Advances in Neural Information Processing Systems, vol. 32. Curran Associates, Inc., Redhook, NY (2019)"},{"issue":"06","key":"408_CR18","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1142\/S0219530516400017","volume":"14","author":"G Blanchard","year":"2016","unstructured":"Blanchard, G., Kr\u00e4mer, N.: Convergence rates of kernel conjugate gradient for random design regression. Anal. Appl. 14(06), 763\u2013794 (2016)","journal-title":"Anal. Appl."},{"key":"408_CR19","unstructured":"Pagliana, N., Rosasco, L.: Implicit Regularization of Accelerated Methods in Hilbert Spaces. In: Advances in Neural Information Processing Systems, vol. 32. Curran Associates, Inc., Redhook, NY (2019)"},{"issue":"102","key":"408_CR20","first-page":"3299","volume":"16","author":"Y Zhang","year":"2015","unstructured":"Zhang, Y., Duchi, J., Wainwright, M.J.: Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates. J. Mach. Learn. Res. 16(102), 3299\u20133340 (2015)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"408_CR21","first-page":"1069","volume":"19","author":"N M\u00fccke","year":"2018","unstructured":"M\u00fccke, N., Blanchard, G.: Parallelizing Spectrally Regularized Kernel Algorithms. J. Mach. Learn. Res. 19(1), 1069\u20131097 (2018)","journal-title":"J. Mach. Learn. Res."},{"issue":"2020","key":"408_CR22","first-page":"34","volume":"21","author":"D Richards","year":"2020","unstructured":"Richards, D., Rebeschini, P.: Graph-dependent implicit regularisation for distributed stochastic subgradient descent. J. Mach. Learn. Res. 21(2020), 34\u201313444 (2020)","journal-title":"J. Mach. Learn. Res."},{"key":"408_CR23","unstructured":"Va\u0161kevi\u010dius, T., Kanade, V., Rebeschini, P.: The Statistical Complexity of Early Stopped Mirror Descent. arXiv:2002.00189 [stat.ML] (2020)"},{"key":"408_CR24","unstructured":"Villa, S., Matet, S., Vu, B.C., Rosasco, L.: Don\u2019t relax: early stopping for convex regularization. arXiv:1707.05422 [stat.ML] (2017)"},{"issue":"1","key":"408_CR25","first-page":"2822","volume":"19","author":"D Soudry","year":"2018","unstructured":"Soudry, D., Hoffer, E., Nacson, M.S., Gunasekar, S., Srebro, N.: The implicit bias of gradient descent on separable data. J. Mach. Learn. Res. 19(1), 2822\u20132878 (2018)","journal-title":"J. Mach. Learn. Res."},{"key":"408_CR26","unstructured":"Ji, Z., Telgarsky, M.: The implicit bias of gradient descent on nonseparable data. In: Conference on learning theory, vol. 99, pp. 1772\u20131798. PMLR, (2019)"},{"issue":"1","key":"408_CR27","first-page":"2718","volume":"17","author":"J Lin","year":"2016","unstructured":"Lin, J., Rosasco, L., Zhou, D.: Iterative regularization for learning with convex loss functions. J. Mach. Learn. Res. 17(1), 2718\u20132755 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"408_CR28","unstructured":"Lin, J., Camoriano, R., Rosasco, L.: Generalization properties and implicit regularization for multiple passes SGM. In: International Conference on Machine Learning, pp. 2340\u20132348. PMLR, (2016)"},{"issue":"25","key":"408_CR29","first-page":"1","volume":"22","author":"Y Lei","year":"2021","unstructured":"Lei, Y., Hu, T., Tang, K.: Generalization performance of multi-pass stochastic gradient descent with convex loss functions. J. Mach. Learn. Res. 22(25), 1\u201341 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"408_CR30","first-page":"499","volume":"2","author":"O Bousquet","year":"2002","unstructured":"Bousquet, O., Elisseeff, A.: Stability and generalization. J. Mach. Learn. Res. 2, 499\u2013526 (2002)","journal-title":"J. Mach. Learn. Res."},{"key":"408_CR31","unstructured":"Chen, Y., Jin, C., Yu, B.: Stability and convergence trade-off of iterative optimization algorithms. arXiv:1804.01619 [stat.ML] (2018)"},{"issue":"3","key":"408_CR32","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1137\/S1052623497331063","volume":"10","author":"DP Bertsekas","year":"2000","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: Gradient convergence in gradient methods with errors. SIAM J. Optim. 10(3), 627\u2013642 (2000)","journal-title":"SIAM J. Optim."},{"key":"408_CR33","unstructured":"Schmidt, M., Roux, N., Bach, F.: Convergence rates of inexact proximal-gradient methods for convex optimization. In: Advances in Neural Information Processing Systems, vol. 24. Curran Associates, Inc., Redhook, NY (2011)"},{"key":"408_CR34","unstructured":"Foster, D.J., Sekhari, A., Sridharan, K.: Uniform convergence of gradients for non-convex learning and optimization. In: Advances in Neural Information Processing Systems, vol. 31. Curran Associates, Inc., Redhook, NY (2018)"},{"key":"408_CR35","unstructured":"Gorbunov, E., Danilova, M., Gasnikov, A.: Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., Redhook, NY (2020)"},{"issue":"1","key":"408_CR36","first-page":"3375","volume":"18","author":"J Lin","year":"2017","unstructured":"Lin, J., Rosasco, L.: Optimal rates for multi-pass stochastic gradient methods. J. Mach. Learn. Res. 18(1), 3375\u20133421 (2017)","journal-title":"J. Mach. Learn. Res."},{"issue":"3\u20134","key":"408_CR37","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 Mach. Learn. 8(3\u20134), 231\u2013357 (2015)","journal-title":"Found. Trends Mach. Learn."},{"key":"408_CR38","volume-title":"Support Vector Machines. Information Science and Statistics","author":"I Steinwart","year":"2008","unstructured":"Steinwart, I., Christmann, A.: Support Vector Machines. Information Science and Statistics. Springer, New York (2008)"},{"key":"408_CR39","doi-asserted-by":"crossref","unstructured":"Bottou, L., Bousquet, O.: The tradeoffs of large scale learning. In: Optimization for Machine Learning, pp. 351\u2013368. MIT Press (2011)","DOI":"10.7551\/mitpress\/8996.003.0015"},{"key":"408_CR40","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001","volume-title":"Concentration Inequalities: A Non-asymptotic Theory of Independence","author":"S Boucheron","year":"2013","unstructured":"Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Non-asymptotic Theory of Independence. Oxford University Press, Oxford (2013)"},{"issue":"1","key":"408_CR41","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1214\/16-AOS1435","volume":"45","author":"S Balakrishnan","year":"2017","unstructured":"Balakrishnan, S., Wainwright, M.J., Yu, B.: Statistical guarantees for the EM algorithm: from population to sample-based analysis. Ann. Stat. 45(1), 77\u2013120 (2017)","journal-title":"Ann. Stat."},{"key":"408_CR42","unstructured":"Holland, M.J., Ikeda, K.: Efficient learning with robust gradient descent. arXiv:1706.00182 [stat.ML] (2018)"},{"key":"408_CR43","unstructured":"Prasad, A., Suggala, A.S., Balakrishnan, S., Ravikumar, P.: Robust estimation via robust gradient estimation. arXiv:1802.06485 [stat.ML] (2018)"},{"issue":"3","key":"408_CR44","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.acha.2018.09.009","volume":"48","author":"J Lin","year":"2020","unstructured":"Lin, J., Rudi, A., Rosasco, L., Cevher, V.: Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces. Appl. Comput. Harmonic Anal. 48(3), 868\u2013890 (2020)","journal-title":"Appl. Comput. Harmonic Anal."},{"key":"408_CR45","unstructured":"Harvey, N., Liaw, C., Plan, Y., Randhawa, S.: Tight analyses for non-smooth stochastic gradient descent. In: Conference on Learning Theory, pp. 1579\u20131613. PMLR (2019)"},{"key":"408_CR46","doi-asserted-by":"crossref","unstructured":"Maurer, A.: A Vector-contraction Inequality for Rademacher Complexities. In: Algorithmic Learning Theory, vol. 9925, pp. 3\u201317. Springer, (2016)","DOI":"10.1007\/978-3-319-46379-7_1"},{"key":"408_CR47","unstructured":"Lei, Y., Tang, K.: Stochastic composite mirror descent: optimal bounds with high probability. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., Redhook, NY (2018)"},{"key":"408_CR48","unstructured":"Derumigny, A., Schmidt-Hieber, J.: On lower bounds for the bias-variance trade-off. arXiv:2006.00278 [stat.ML] (2020)"},{"key":"408_CR49","first-page":"463","volume":"3","author":"PL Bartlett","year":"2002","unstructured":"Bartlett, P.L., Mendelson, S.: Rademacher and gaussian complexities: risk bounds and structural results. J. Mach. Learn. Res. 3, 463\u2013482 (2002)","journal-title":"J. Mach. Learn. Res."},{"key":"408_CR50","volume-title":"High-dimensional Probability. Cambridge Series in Statistical and Probabilistic Mathematics","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-dimensional Probability. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2018)"},{"key":"408_CR51","doi-asserted-by":"publisher","DOI":"10.1017\/9781108627771","volume-title":"High-dimensional Statistics: A Non-asymptotic Viewpoint","author":"MJ Wainwright","year":"2019","unstructured":"Wainwright, M.J.: High-dimensional Statistics: A Non-asymptotic Viewpoint. Cambridge University Press, Cambridge (2019)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00408-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-022-00408-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00408-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T05:27:11Z","timestamp":1700976431000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-022-00408-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,25]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["408"],"URL":"https:\/\/doi.org\/10.1007\/s10589-022-00408-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2022,8,25]]},"assertion":[{"value":"20 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"(Not applicable).","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"(Not applicable).","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"(Not applicable).","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}