The Heavy-Tailed Methods in Machine Learning

随机梯度下降及其变体是解决机器学习问题的核心算法，在实践中表现优异。然而，一个普遍的理论解释他们的成功仍然缺乏。一种流行的方法是对梯度噪声施加结构，通常由高斯分布或其他轻尾分布建模。然而，许多经验和最近的一些理论工作挑战了这些假设，要求理解机器学习中的重尾分布和由此产生的现象。在这个项目中，将建立一个理论框架，以理解和解释为什么以及如何在流行的机器学习算法中出现重尾分布，以及重尾如何更好地解释它们的成功，弥合理论与实践之间的差距。该项目的结果预计将影响数学界以及数据科学和机器学习社区的开发人员和实践者。在本项目中，将获得重尾随机梯度下降及其基于加速动量的方法和连续时间逼近的理论收敛性质和性能保证。进一步的理论性质，如亚稳性将被研究，以获得对这些重尾方法的进一步理解。本文将提出一种新的重尾自适应朗格万算法及其变体，并对抽样和非凸随机优化的理论保证进行研究。这样的目标需要结合广泛的思想和数学工具，从应用概率，连续优化，统计和数值分析。基于这样的数学发展，该项目将开发和研究具有理论保证的重尾算法，可以解决大规模机器学习问题，最终建立一个数学理论来解释重尾分布和机器学习中出现的其他重要现象的原因和含义。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Stochastic gradient descent and its variants are core algorithms for solving machine learning problems and work remarkably well in practice. However, a general theory that explains their success is still lacking. One popular approach is to impose structure on the gradient noise, typically modeled by Gaussian or other light-tailed distributions. However, many empirical and some recent theoretical works challenge these assumptions, calling for an understanding of heavy-tailed distributions and resulting phenomena in machine learning. In this project, a theoretical framework will be built towards understanding and explaining why and how heavy tailed distributions arise in popular machine learning algorithms, and how heavy tails can better explain their success, bridging a gap between theory and practice. The results derived from this project are expected to impact the mathematics community as well as developers and practitioners in the data science and machine learning communities. In this project, theoretical convergence properties and performance guarantees will be obtained for heavy-tailed stochastic gradient descent, their accelerated momentum-based methods, and continuous-time approximations. Further theoretical properties such as metastability will be studied to gain a further understanding of these heavy-tailed methods. A novel heavy-tailed adaptive Langevin algorithm and its variants will be developed and the theoretical guarantees will be studied for both sampling and non-convex stochastic optimization. Such an objective requires combining a broad set of ideas and mathematical tools from applied probability, continuous optimization, statistics and numerical analysis. Based on such mathematical developments the project will develop and study heavy-tailed algorithms with theoretical guarantees that can solve large-scale machine learning problems, ultimately building up a mathematical theory to explain the cause and implications of heavy-tailed distributions and other important phenomena that arise in machine learning.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.