Zero-Order and Stochastic Methods for Large-Scale Optimization

点击翻译按钮获取中文摘要

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.