{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T21:37:26Z","timestamp":1777498646436,"version":"3.51.4"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031434204","type":"print"},{"value":"9783031434211","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43421-1_18","type":"book-chapter","created":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T20:37:24Z","timestamp":1694983044000},"page":"301-315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Convergence of\u00a0Random Reshuffling Under Over-Parameterization and\u00a0the\u00a0Polyak-\u0141ojasiewicz Condition"],"prefix":"10.1007","author":[{"given":"Chen","family":"Fan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Thrampoulidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,18]]},"reference":[{"key":"18_CR1","first-page":"17526","volume":"33","author":"K Ahn","year":"2020","unstructured":"Ahn, K., Yun, C., Sra, S.: Sgd with shuffling: optimal rates without component convexity and large epoch requirements. Adv. Neural. Inf. Process. Syst. 33, 17526\u201317535 (2020)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"18_CR2","unstructured":"Bassily, R., Belkin, M., Ma, S.: On exponential convergence of SGD in non-convex over-parametrized learning. arXiv preprint arXiv:1811.02564 (2018)"},{"key":"18_CR3","unstructured":"Bottou, L.: Curiously fast convergence of some stochastic gradient descent algorithms. In: Proceedings of the Symposium on Learning and Data Science, Paris, vol. 8, pp. 2624\u20132633 (2009)"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-3-642-35289-8_25","volume-title":"Neural Networks: Tricks of the Trade","author":"L Bottou","year":"2012","unstructured":"Bottou, L.: Stochastic gradient descent tricks. In: Montavon, G., Orr, G.B., M\u00fcller, K.-R. (eds.) Neural Networks: Tricks of the Trade. LNCS, vol. 7700, pp. 421\u2013436. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-35289-8_25"},{"issue":"2","key":"18_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/16M1080173","volume":"60","author":"L Bottou","year":"2018","unstructured":"Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning. SIAM Rev. 60(2), 223\u2013311 (2018)","journal-title":"SIAM Rev."},{"issue":"5","key":"18_CR6","doi-asserted-by":"publisher","first-page":"1177","DOI":"10.1007\/s11590-018-1331-1","volume":"13","author":"V Cevher","year":"2019","unstructured":"Cevher, V., V\u0169, B.C.: On the linear convergence of the stochastic gradient method with constant step-size. Optim. Lett. 13(5), 1177\u20131187 (2019)","journal-title":"Optim. Lett."},{"key":"18_CR7","unstructured":"Cha, J., Lee, J., Yun, C.: Tighter lower bounds for shuffling SGD: random permutations and beyond. arXiv preprint arXiv:2303.07160 (2023)"},{"issue":"1","key":"18_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S1446788700022126","volume":"39","author":"BD Craven","year":"1985","unstructured":"Craven, B.D., Glover, B.M.: Invex functions and duality. J. Aust. Math. Soc. 39(1), 1\u201320 (1985)","journal-title":"J. Aust. Math. Soc."},{"key":"18_CR9","unstructured":"Du, S.S., Zhai, X., Poczos, B., Singh, A.: Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054 (2018)"},{"key":"18_CR10","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)"},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-019-01440-w","volume":"186","author":"M G\u00fcrb\u00fczbalaban","year":"2021","unstructured":"G\u00fcrb\u00fczbalaban, M., Ozdaglar, A., Parrilo, P.A.: Why random reshuffling beats stochastic gradient descent. Math. Program. 186(1), 49\u201384 (2021)","journal-title":"Math. Program."},{"key":"18_CR12","unstructured":"Haochen, J., Sra, S.: Random shuffling beats SGD after finite epochs. In: International Conference on Machine Learning, pp. 2624\u20132633. PMLR (2019)"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/978-3-319-46128-1_50","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"H Karimi","year":"2016","unstructured":"Karimi, H., Nutini, J., Schmidt, M.: Linear convergence of gradient and proximal-gradient methods under the Polyak-\u0141ojasiewicz Condition. In: Frasconi, P., Landwehr, N., Manco, G., Vreeken, J. (eds.) ECML PKDD 2016. LNCS (LNAI), vol. 9851, pp. 795\u2013811. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-46128-1_50"},{"key":"18_CR14","unstructured":"Koloskova, A., Doikov, N., Stich, S.U., Jaggi, M.: Shuffle SGD is always better than SGD: improved analysis of SGD with arbitrary data orders. arXiv preprint arXiv:2305.19259 (2023)"},{"key":"18_CR15","unstructured":"Lai, Z., Lim, L.H.: Recht-r\u00e9 noncommutative arithmetic-geometric mean conjecture is false. In: International Conference on Machine Learning, pp. 5608\u20135617. PMLR (2020)"},{"issue":"11","key":"18_CR16","doi-asserted-by":"publisher","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Y LeCun","year":"1998","unstructured":"LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86(11), 2278\u20132324 (1998)","journal-title":"Proc. IEEE"},{"key":"18_CR17","unstructured":"Li, X., Milzarek, A., Qiu, J.: Convergence of random reshuffling under the kurdyka-$$\\{$$$$\\backslash $$L$$\\}$$ ojasiewicz inequality. arXiv preprint arXiv:2110.04926 (2021)"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.acha.2021.12.009","volume":"59","author":"C Liu","year":"2022","unstructured":"Liu, C., Zhu, L., Belkin, M.: Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Appl. Comput. Harmon. Anal. 59, 85\u2013116 (2022)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"18_CR19","unstructured":"Loizou, N., Vaswani, S., Laradji, I.H., Lacoste-Julien, S.: Stochastic polyak step-size for SGD: an adaptive learning rate for fast convergence. In: International Conference on Artificial Intelligence and Statistics, pp. 1306\u20131314. PMLR (2021)"},{"key":"18_CR20","unstructured":"Lojasiewicz, S.: A topological property of real analytic subsets. Coll. du CNRS, Les \u00e9quations aux d\u00e9riv\u00e9es partielles 117(87\u201389), 2 (1963)"},{"key":"18_CR21","unstructured":"Lu, Y., Guo, W., Sa, C.D.: Grab: Finding provably better data permutations than random reshuffling (2023)"},{"key":"18_CR22","unstructured":"Ma, S., Zhou, Y.: Understanding the impact of model incoherence on convergence of incremental SGD with random reshuffle. In: International Conference on Machine Learning, pp. 6565\u20136574. PMLR (2020)"},{"key":"18_CR23","first-page":"17309","volume":"33","author":"K Mishchenko","year":"2020","unstructured":"Mishchenko, K., Khaled, A., Richt\u00e1rik, P.: Random reshuffling: simple analysis with vast improvements. Adv. Neural. Inf. Process. Syst. 33, 17309\u201317320 (2020)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"18_CR24","unstructured":"Mishkin, A.: Interpolation, growth conditions, and stochastic gradient descent. Ph.D. thesis, University of British Columbia (2020)"},{"key":"18_CR25","unstructured":"Moulines, E., Bach, F.: Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems 24 (2011)"},{"key":"18_CR26","unstructured":"Nagaraj, D., Jain, P., Netrapalli, P.: Sgd without replacement: sharper rates for general smooth convex functions. In: International Conference on Machine Learning, pp. 4703\u20134711. PMLR (2019)"},{"key":"18_CR27","unstructured":"Needell, D., Ward, R., Srebro, N.: Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Advances in neural information processing systems 27 (2014)"},{"issue":"1","key":"18_CR28","first-page":"9397","volume":"22","author":"LM Nguyen","year":"2021","unstructured":"Nguyen, L.M., Tran-Dinh, Q., Phan, D.T., Nguyen, P.H., Van Dijk, M.: A unified convergence analysis for shuffling-type gradient methods. J. Mach. Learn. Res. 22(1), 9397\u20139440 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"18_CR29","unstructured":"Oymak, S., Soltanolkotabi, M.: Overparameterized nonlinear learning: gradient descent takes the shortest path? In: International Conference on Machine Learning, pp. 4951\u20134960. PMLR (2019)"},{"issue":"4","key":"18_CR30","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)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"18_CR31","first-page":"45","volume":"34","author":"B Polyak","year":"1973","unstructured":"Polyak, B., Tsypkin, Y.Z.: Pseudogradient adaptation and training algorithms. Autom. Remote. Control. 34, 45\u201367 (1973)","journal-title":"Autom. Remote. Control."},{"key":"18_CR32","unstructured":"Rajput, S., Gupta, A., Papailiopoulos, D.: Closing the convergence gap of SGD without replacement. In: International Conference on Machine Learning, pp. 7964\u20137973. PMLR (2020)"},{"key":"18_CR33","unstructured":"Recht, B., R\u00e9, C.: Toward a noncommutative arithmetic-geometric mean inequality: Conjectures, case-studies, and consequences. In: Conference on Learning Theory, pp. 11\u20131. JMLR Workshop and Conference Proceedings (2012)"},{"key":"18_CR34","unstructured":"Safran, I., Shamir, O.: How good is sgd with random shuffling? In: Conference on Learning Theory, pp. 3250\u20133284. PMLR (2020)"},{"key":"18_CR35","first-page":"15151","volume":"34","author":"I Safran","year":"2021","unstructured":"Safran, I., Shamir, O.: Random shuffling beats SGD only after many epochs on ill-conditioned problems. Adv. Neural. Inf. Process. Syst. 34, 15151\u201315161 (2021)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"18_CR36","unstructured":"Schmidt, M., Roux, N.L.: Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv:1308.6370 (2013)"},{"issue":"2","key":"18_CR37","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1109\/TIT.2018.2854560","volume":"65","author":"M Soltanolkotabi","year":"2018","unstructured":"Soltanolkotabi, M., Javanmard, A., Lee, J.D.: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Trans. Inf. Theory 65(2), 742\u2013769 (2018)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"18_CR38","unstructured":"Vaswani, S., Bach, F., Schmidt, M.: Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1195\u20131204. PMLR (2019)"},{"key":"18_CR39","unstructured":"Vaswani, S., Mishkin, A., Laradji, I., Schmidt, M., Gidel, G., Lacoste-Julien, S.: Painless stochastic gradient: interpolation, line-search, and convergence rates. Advances in neural information processing systems 32 (2019)"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases: Research Track"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43421-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T20:44:27Z","timestamp":1694983467000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43421-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031434204","9783031434211"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43421-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"18 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The contribution is the theoretical analysis of an existing algorithm, so it does not have direct societal or ethical implications.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Statement"}},{"value":"ECML PKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecml2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/2023.ecmlpkdd.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"CMT","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"829","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"196","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.63","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Applied Data Science Track: 239 submissions, 58 accepted papers; Demo Track: 31 submissions, 16 accepted papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}