Zero-Order and Stochastic Methods for Large-Scale Optimization

几十年来，人工智能（AI）的前景一直是公众和私人都感兴趣的话题。由于机器学习领域的迅速发展和扩大，它最近蓬勃发展，在感知任务中取得了令人印象深刻的成果，并已成为现代人工智能的核心技术。从机器学习中产生的智能系统——比如搜索引擎、推荐平台、语音和图像识别软件——已经成为现代社会不可或缺的一部分。机器学习技术植根于统计学，严重依赖于数值算法的效率，它利用了世界上日益强大的计算平台和非常大的数据集的可用性。机器学习的支柱之一是优化，在这种情况下，优化涉及系统参数的数值计算，该系统旨在根据尚未见过的数据做出决策。也就是说，根据当前可用的数据，选择这些参数对于给定的学习问题是最优的。优化在机器学习中发挥的核心作用激励了许多研究团体解决更具挑战性的机器学习问题，并设计出更广泛适用的新优化方法。该项目致力于开发新一代优化方法，通过减少计算时间和允许更大和更复杂模型的制定，有助于推进机器学习领域。这将有助于人工智能扩展到医学、机器人和物流等许多领域。本项目为研究生提供研究训练机会。从技术上讲，本提案的目标是为随机优化问题开发新的算法，例如机器学习，统计学和黑盒模拟中出现的问题。它由两个相互关联的项目组成，包括算法设计、收敛分析和实际应用的数值测试。第一个项目处理约束优化问题，其中目标函数是随机的，约束是确定的。所提出的方法使用不同的样本量来逐渐减小梯度近似中的方差；它们已经在无约束优化的背景下进行了研究，但将它们扩展到约束设置并不简单，因为用于执行约束的投影或近端算子引入了不连续。第二个课题研究了求解无约束噪声优化问题的零阶方法。与使用插值技术构建目标函数二次模型的无导数方法不同，所提出的方法在计算噪声函数梯度的良好近似值方面投入了大量精力，并将二次模型的构建委托给准牛顿更新。这两个项目是相互关联的，当结合在一起时，将产生可扩展到数百万个变量并易于并行化的算法。它们的效率将在解决强化学习中出现的问题中得到证明。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The promise of artificial intelligence (AI) has been a topic of both public and private interest for decades. It has recently blossomed thanks to the rapidly evolving and expanding field of machine learning, which has produced impressive results in perceptual tasks and has emerged as the core technology of modern AI. The intelligent systems that have been borne out of machine learning - such as search engines, recommendation platforms, and speech and image recognition software - have become an indispensable part of modern society. Rooted in statistics and relying heavily on the efficiency of numerical algorithms, machine learning techniques capitalize on the world's increasingly powerful computing platforms and the availability of very large data sets. One of the pillars of machine learning is optimization, which, in this context, involves the numerical computation of parameters for a system designed to make decisions based on yet unseen data. That is, based on currently available data, these parameters are chosen to be optimal with respect to a given learning problem. The central role that optimization plays in machine learning has inspired great numbers in various research communities to tackle even more challenging machine learning problems, and to design new optimization methods that are more widely applicable. This project is devoted to the development of a new generation of optimization methods that will help advance the field of machine learning by reducing computing time and allowing for the formulation of larger and more complex models. This will help AI expand into many domains such as medicine, robotics and logistics. This project provides research training opportunities for graduate students.In technical terms, the goal of this proposal is to develop new algorithms for stochastic optimization problems, such as those arising in machine learning, statistics and black-box simulations. It consists of two interrelated projects encompassing algorithm design, convergence analysis, and numerical testing on realistic applications. The first project deals with constrained optimization problems in which the objective function is stochastic and the constraints are deterministic. The proposed methods use varying sample sizes to gradually reduce the variance in the gradient approximation; they have been studied in the context of unconstrained optimization, but their extension to the constrained setting is not simple because the projections or proximal operators used to enforce the constraints introduce discontinuities. The second project studies zero-order methods for the solution of noisy unconstrained optimization problems. Unlike derivative-free methods that construct quadratic models of the objective function using interpolation techniques, the proposed methods invest significant effort in computing a good approximation to the gradient of the noisy function and delegate the construction of a quadratic model to quasi-Newton updating. The two projects are interrelated and when combined will yield algorithms that scale into the millions of variables and parallelize easily. Their efficiency will be demonstrated in the solution of problems arising in reinforcement 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.