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

AF：RI：小：凸和最小-最大优化中驻点的计算高效近似

• 批准号: 2007757
• 负责人: Jelena Diakonikolas
• 金额: $ 35万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007757&HistoricalAwards=false
• 关键词: AF; RI; Small; Computationally; Efficient

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.

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

项目成果

Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization

• 发表时间: 2020-10
• 作者: Jelena Diakonikolas;C. Daskalakis;Michael I. Jordan

Robustly Learning a Single Neuron via Sharpness

• DOI: 10.48550/arxiv.2306.07892
• 发表时间: 2023-06
• 作者: Puqian Wang;Nikos Zarifis;Ilias Diakonikolas;Jelena Diakonikolas

Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise

具有随机分类噪声的学习边缘半空间的信息计算权衡

• 发表时间: 2023
• 期刊: Proceedings of Thirty Sixth Conference on Learning Theory
• 作者: Diakonikolas, Ilias;Diakonikolas, Jelena;Kane, Daniel;Wang, Puqian;Zarifis, Nikos
• 通讯作者: Zarifis, Nikos

Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise

学习具有随机分类噪声的高斯半空间的近乎最优界限

• 发表时间: 2023
• 期刊: 37th Conference on Neural Information Processing Systems (NeurIPS 2023
• 作者: Diakonikolas, Ilias;Diakonikolas, Jelena;Kane, Daniel;Wang, Puqian;Zarifis, Nikos
• 通讯作者: Zarifis, Nikos

Generalized Momentum-Based Methods: A Hamiltonian Perspective

• DOI: 10.1137/20m1322716
• 发表时间: 2019-06
• 期刊: ArXiv
• 作者: Jelena Diakonikolas;Michael I. Jordan