AF: RI: Small: Computationally Efficient Approximation of Stationary Points in Convex and Min-Max Optimization

优化几乎渗透到生活的方方面面，从自然选择和进化到技术和经济发展。在现代数据科学中，优化算法是在数据中发现模式、创建解释和模仿模式的模型以及做出预测的核心引擎。该项目的主要目标是推进优化的理论基础，并利用所获得的见解来开发广泛适用、适应不同数据模型和可扩展的新算法，以便它们可以应用于更加雄心勃勃的数据科学应用。该项目中理论框架发展的指导原则之一是优化算法和规律之间的平行关系，例如控制物理系统行为的最小作用原理。更具体地说，这个项目的目标是进一步理解优化算法收敛到平稳点（定义为具有小梯度范数的点）的速度有多快。在凸优化中，一个最基本的事实是，每个驻点也是全局函数的最小值。然而，有效地计算近平稳点的问题与有效地逼近函数最小值的问题是完全不同的，在其中一个准则下表现出最优收敛率的方法通常在两个准则下都表现出最优收敛率。特别是，Nesterov的加速梯度方法在最小化光滑（梯度lipschitz）凸函数方面是迭代复杂度最优的，但在寻找它们的近平稳点方面是次优的。虽然最小化凸函数的复杂性是众所周知的，但对于寻找近平稳点的复杂性却知之甚少。这种令人不安的理解差距不仅对通用优化算法造成了严重的算法限制，而且在许多应用领域也是如此。该项目的主要重点是通过开发一个通用框架来分析凸优化中的平稳点收敛及其推广，利用动力系统，单调算子理论和不动点理论的技术工具来缩小这一差距。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Optimization permeates almost every aspect of life, from natural selection and evolution to technological and economic development. Within modern data science, optimization algorithms are the core engine for finding patterns in the data, creating models that explain and mimic them, and making predictions. The primary goal of this project is to advance the theoretical foundations of optimization and leverage the obtained insights to develop new algorithms that are broadly applicable, adaptive to different data models, and scalable, so that they can be applied to the ever-more ambitious data-science applications. One of the guiding principles for the development of theoretical frameworks in this project are parallels between optimization algorithms and laws, such as the principle of least action, governing the behavior of physical systems. More concretely, the goal of this project is to further the understanding of how fast it is possible for optimization algorithms to converge to stationary points, defined as the points with small gradient norms. In convex optimization, one of the most fundamental facts is that every stationary point is also a global function minimum. However, the problem of efficiently computing near-stationary points is quite different from the problem of efficiently approximating the function minima, and methods that exhibit optimal convergence rates under one of the criteria do not in general exhibit optimal convergence rates under both. In particular, Nesterov’s accelerated gradient method is iteration-complexity-optimal in terms of minimizing smooth (gradient-Lipschitz) convex functions, but suboptimal in terms of finding their near-stationary points. While the complexity of minimizing convex functions is well-understood, much less is known about the complexity of finding near-stationary points. This troubling gap in understanding causes severe algorithmic limitations not only for general-purpose optimization algorithms, but also in a number of application areas. The primary focus of this project is to close this gap by developing a general framework for the analysis of convergence to stationary points in convex optimization and its generalizations, leveraging technical tools from dynamical systems, monotone-operator theory, and fixed-point theory.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.