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

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

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.