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的法定任务，并通过评估了基金会的评估，并通过评估了CRCRITIAL和BRODIT和BRODIT和BRODIT和BRODITIAL和BRODITIAL和BRODITICAILAIN和BRODITIAL和BRODITICAITIAS。

项目成果

Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization

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

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

Robustly Learning a Single Neuron via Sharpness

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

Generalized Momentum-Based Methods: A Hamiltonian Perspective

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

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