Complexity of Normalized Stochastic First-Order Methods with Momentum Under Heavy-Tailed Noise

References

• [1] Arjevani Y, Carmon Y, Duchi JC, Foster DJ, Srebro N, Woodworth B (2023) Lower bounds for non-convex stochastic optimization. Math. Programming 199(1):165–214.Crossref, Google Scholar
• [2] Bottou L, Curtis FE, Nocedal J (2018) Optimization methods for large-scale machine learning. SIAM Rev. 60(2):223–311.Crossref, Google Scholar
• [3] Carmon Y, Duchi JC, Hinder O, Sidford A (2017) “Convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (JMLR.org, Cambridge, MA), 654–663.Google Scholar
• [4] Cutkosky A, Mehta H (2020) Momentum improves normalized SGD. Daumé H, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 119 (JMLR.org, Cambridge, MA), 2260–2268.Google Scholar
• [5] Cutkosky A, Mehta H (2021) High-probability bounds for non-convex stochastic optimization with heavy tails. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Advances in Neural Information Processing Systems, vol. 34 (Curran Associates, Red Hook, NY), 4883–4895.Google Scholar
• [6] Cutkosky A, Orabona F (2019) Momentum-based variance reduction in non-convex SGD. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Red Hook, NY), 15236--15245.Google Scholar
• [7] Fang C, Li CJ, Lin Z, Zhang T (2018) Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Red Hook, NY), 687--697.Google Scholar
• [8] Gao Y, Rodomanov A, Stich SU (2024) Non-convex stochastic composite optimization with Polyak momentum. Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, Berkenkamp F, eds. Proc. 41st Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 235 (JMLR.org, Cambridge, MA), 14826–14843.Google Scholar
• [9] Ghadimi S, Lan G (2013) Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim. 23(4):2341–2368.Crossref, Google Scholar
• [10] Ghadimi S, Lan G (2016) Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Programming 156(1):59–99.Crossref, Google Scholar
• [11] Gurbuzbalaban M, Simsekli U, Zhu L (2021) The heavy-tail phenomenon in SGD. Marina M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 139 (JMLR.org, Cambridge, MA), 3964–3975.Google Scholar
• [12] He K, Zhang X, Ren S, Sun J (2016) Deep residual learning for image recognition. 2016 IEEE Conf. Comput. Vision Pattern Recognition (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 770–778.Google Scholar
• [13] Horn RA, Johnson CR (2012) Matrix Analysis (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [14] Hübler F, Fatkhullin I, He N (2025) From gradient clipping to normalization for heavy tailed SGD. Li Y, Mandt S, Agrawal S, Khan E, eds. Proc. 28th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 258 (JMLR.org, Cambridge, MA), 2413–2421.Google Scholar
• [15] Humpherys J, Jarvis TJ (2020) Foundations of Applied Mathematics Volume 2: Algorithms, Approximation, Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [16] Khaled A, Richtárik P (2023) Better theory for SGD in the nonconvex world. Trans. Machine Learn. Res., https://openreview.net/forum?id=AU4qHN2VkS.Google Scholar
• [17] Klamkin M, Newman DJ (1970) Extensions of the Weierstrass product inequalities. Math. Magazine 43(3):137–141.Crossref, Google Scholar
• [18] Lei L, Ju C, Chen J, Jordan MI (2017) Non-convex finite-sum optimization via SCSG methods. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Red Hook, NY), 2348--2358.Google Scholar
• [19] Li Z, Bao H, Zhang X, Richtárik P (2021) PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. Marina M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 139 (JMLR.org, Cambridge, MA), 6286–6295.Google Scholar
• [20] Lin TY, Maire M, Belongie S, Hays J, Perona P, Ramanan D, Dollár P, Zitnick CL (2014) Microsoft COCO: Common objects in context. Fleet D, Pajdla T, Schiele B, Tuytelaars T, eds. Computer Vision (Springer, Cham, Switzerland), 740–755.Google Scholar
• [21] Liu Z, Zhou Z (2025) Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. Yue Y, Garg A, Peng N, Sha F, Yu R, eds. Internat. Conf. Learn. Representations (OpenReview), 92529--92554.Google Scholar
• [22] Liu L, Wang Y, Zhang L (2024) High-probability bound for non-smooth non-convex stochastic optimization with heavy tails. Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, Berkenkamp F, eds. Proc. 41st Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 235 (JMLR.org, Cambridge, MA), 32122–32138.Google Scholar
• [23] Liu Z, Zhang J, Zhou Z (2023) Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. Neu G, Lorenzo Rosasco L, eds. Proc. 36th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 195 (JMLR.org, Cambridge, MA), 2266–2290.Google Scholar
• [24] Nguyen LM, Liu J, Scheinberg K, Takáč M (2017) SARAH: A novel method for machine learning problems using stochastic recursive gradient. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (JMLR.org, Cambridge, MA), 2613–2621.Google Scholar
• [25] Nguyen TD, Nguyen TH, Ene A, Nguyen H (2023) Improved convergence in high probability of clipped gradient methods with heavy tailed noise. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds. Advances in Neural Information Processing Systems, vol. 36 (Curran Associates, Red Hook, NY), 24191–24222.Crossref, Google Scholar
• [26] Plummer BA, Wang L, Cervantes CM, Caicedo JC, Hockenmaier J, Lazebnik S (2015) Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models. Internat. Conf. Comput. Vision (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 2641–2649.Google Scholar
• [27] Radford A, Kim JW, Hallacy C, Ramesh A, Goh G, Agarwal S, Sastry G, et al. (2021) Learning transferable visual models from natural language supervision. Marina M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 139 (JMLR.org, Cambridge, MA), 8748–8763.Google Scholar
• [28] Rodomanov A, Nesterov Y (2020) Smoothness parameter of power of Euclidean norm. J. Optim. Theory Appl. 185(2):303–326.Crossref, Google Scholar
• [29] Sadiev A, Danilova M, Gorbunov E, Horváth S, Gidel G, Dvurechensky P, Gasnikov A, Richtárik P (2023) High-probability bounds for stochastic optimization and variational inequalities: The case of unbounded variance. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 202 (JMLR.org, Cambridge, MA), 29563–29648.Google Scholar
• [30] Sanh V, Debut L, Chaumond J, Wolf T (2019) DistilBERT, a distilled version of BERT: Smaller, faster, cheaper and lighter. Preprint, submitted October 2, https://arxiv.org/abs/1910.01108.Google Scholar
• [31] Sharma P, Ding N, Goodman S, Soricut R (2018) Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning. Gurevych I, Miyao Y, eds. Proc. 56th Annual Meeting Assoc. Comput. Linguistics (Association for Computational Linguistics, Kerrville, TX), 2556–2565.Google Scholar
• [32] Simsekli U, Sagun L, Gurbuzbalaban M (2019a) A tail-index analysis of stochastic gradient noise in deep neural networks. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 97 (JMLR.org, Cambridge, MA), 5827–5837.Google Scholar
• [33] Simsekli U, Gürbüzbalaban M, Nguyen TH, Richard G, Sagun L (2019b) On the heavy-tailed theory of stochastic gradient descent for deep neural networks. Preprint, submitted November 29, https://arxiv.org/abs/1912.00018.Google Scholar
• [34] Sun T, Liu X, Yuan K (2025) Revisiting gradient normalization and clipping for nonconvex SGD under heavy-tailed noise: Necessity, sufficiency, and acceleration. J. Machine Learn. Res. 26(237):1–42.Google Scholar
• [35] Touvron H, Lavril T, Izacard G, Martinet X, Lachaux MA, Lacroix T, Rozière B, et al. (2023) LLaMA: Open and efficient foundation language models. Preprint, submitted February 27, https://arxiv.org/abs/2302.13971.Google Scholar
• [36] Zhang J, Karimireddy SP, Veit A, Kim S, Reddi S, Kumar S, Sra S (2020) Why are adaptive methods good for attention models? Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Red Hook, NY), 15383–15393.Google Scholar