Collaborative Research: AF: Small: Adaptive Optimization of Stochastic and Noisy Function

人工智能科学，特别是机器学习技术，对现代社会产生了巨大的影响。预计这种影响在未来只会越来越大。机器学习的核心是训练智能（计算机）系统参数的过程，这需要数学优化领域的应用数学技术。ML最近的许多成功，如计算机视觉和自然语言处理，都是通过使用某种数学优化算法实现的。该算法允许智能系统通过从大规模数据集中迭代随机选择数据点进行学习。这种随机抽样是绝对必要的，否则任何智能系统的学习过程都会随着可用数据量的增加而减慢。然而，尽管最近取得了这些成功，像这样的优化技术仍然有一些根本性的缺点，这些缺点阻碍了它们在下一代ML任务中发挥作用。例如，算法的每一个应用都需要一个仔细的数据依赖的调整过程，这可能会导致一个智能系统的训练需要在超级计算机上进行数周或数月的计算。避免这种计算开销的一个途径是通过设计“自适应”调整自己的优化技术。本课题的目标是为这种自适应算法的设计和提供理论保障。前面提到的算法被称为随机梯度（SG）算法，已经有各种先前提出的增强和扩展。然而，这些算法中的许多也具有非自适应的缺点，这意味着它们在实践中的成功应用需要昂贵的“超参数”调优工作。本项目中考虑的ML“随机优化”设置的自适应算法是基于“确定性优化”文献中各种成功的方法。这些方法包括所谓的“线搜索”和“信任区域”方法。然而，由于这两种方法都不能保证最优的最坏情况复杂度，因此项目的重点是设计自适应最优复杂度方法，例如所谓的“三次正则化”算法。对于随机设置的自适应三次正则化算法的设计将通过建立一个将自适应最小化视为“更新-奖励”随机过程的理论框架来实现。这项工作将结合数学优化和随机过程文献的分析技术，并将为应用数学、计算机科学、统计学和各种工程领域的研究人员提供坚实的理论和实践基础。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The science of artificial intelligence, and the technology of machine learning (ML) in particular, has had a huge impact on modern society. This impact is only expected to grow in the future. At the heart of ML is the process of training the parameters of an intelligent (computer) system, which requires applied-mathematics techniques in the area known as mathematical optimization. The many recent successes of ML, such as in computer vision and natural-language processing, have been made possible with the use of a certain mathematical-optimization algorithm. This algorithm allows the intelligent system to learn through the iterative random selection of data points from within a large-scale dataset. This random sampling is absolutely essential, since otherwise the learning process of any intelligent system would be slowed as the amount of available data increases. However, despite these recent successes, optimization techniques such as this one have fundamental shortcomings that impede them from being effective for next-generation ML tasks. For example, each application of the algorithm requires a careful data-dependent tuning process, which may cause the training of an intelligent system for a single task to require weeks or months of computation on a supercomputer. One avenue for avoiding such computational expense is through the design of optimization techniques that "adaptively" tune themselves. The goals of this project are to design and provide theoretical guarantees for such adaptive algorithms.There have been various previously proposed enhancements and extensions to the aforementioned algorithm, known as the stochastic gradient (SG) algorithm. However, many of these algorithms also possess the shortcoming of being nonadaptive, meaning that their successful application in practice requires expensive "hyperparameter" tuning efforts. The adaptive algorithms considered in this project for the "stochastic optimization" setting of ML are based on the various successful methodologies in the "deterministic optimization" literature. These include so-called "line search" and "trust region" methodologies. However, since neither of these methodologies result in optimal worst-case complexity guarantees, the focus of the project is on the design of adaptive optimal-complexity methods, such as so-called "cubic-regularization" algorithms. The design of adaptive cubic-regularization algorithms for the stochastic setting will be achieved by building on a theoretical framework that views adaptive minimization as a "renewal-reward" stochastic process. This work will combine analytical techniques from the mathematical-optimization and stochastic-process literatures, and will provide a solid theoretical and practical foundation for researchers working in applied mathematics, computer science, statistics, and various engineering fields.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.