CAREER: Navigating the Curse of Dimensionality in Euclidean Optimization Problems

职业：解决欧几里得优化问题中的维数灾难

• 批准号: 2337993
• 负责人: Erik Waingarten
• 金额: $ 64.86万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-06-01 至 2029-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2337993&HistoricalAwards=false
• 关键词: CAREER; Navigating; Curse; Dimensionality; Euclidean

This project aims to study the "curse of dimensionality," the phenomenon that many computational problems for geometric data become exponentially harder as the dimension increases. Advancements in deep learning have demonstrated that high-dimensional geometry and large-scale computation can model many aspects of the world. Even notions that at first glance appear to be non-geometric, such as the meaning of a word or the artistic style of a painting, can often be captured by the richness of a high-dimensional space. However, this richness is also the source of intractability in algorithms that are designed to answer questions and perform tasks, and nearly all applications of high-dimensional computing will face, sooner or later, the curse of dimensionality. This research seeks algorithms to overcome this curse, where the guiding question is: which geometric optimization problems admit efficient algorithms with accurate approximations? Given the massive increases in scale of modern data science applications, new algorithmic techniques are needed to drive further development. The project aims to develop the core algorithmic principles for problems that can be efficiently solved, and to identify the fundamental limitations of problems that do not admit efficient algorithms. The educational plan includes enhancements to course pedagogy through homework modules that guide students through difficult concepts through a process of "discovery." The project also includes mentoring of graduate students and postdoctoral fellows and broadening participation through the LatinX in AI (LXAI) organization. This project proceeds along three key algorithmic directions, each of which highlights a broader theme in geometric optimization that is not yet well-understood. These are (1) handling global constraints (for example, in computing optimal transports); (2) optimizing for the object versus the cost (as in certain hierarchical clustering problems); and (3) circumventing hardness results (as in the closest pair problem). Each challenge comes with its suite of foundational questions, conjectures, and algorithmic principles that this project will address. The guiding principles behind the research plan are dimension reduction and locality (taken together, these principles use dimension reduction to enhance nearest neighbor search). Driven by the theoretical advancements, the project will also develop practical implementations and benchmark tools for large-scale geometric optimization, as a way to invite innovation beyond 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.

这个项目旨在研究“维数灾难”，即随着维数的增加，许多几何数据的计算问题变得指数级困难的现象。深度学习的进步已经证明，高维几何和大规模计算可以对世界的许多方面进行建模。 即使是乍一看似乎是非几何的概念，例如一个词的含义或一幅画的艺术风格，也常常可以被高维空间的丰富性所捕获。然而，这种丰富性也是设计用于回答问题和执行任务的算法的棘手性的来源，并且几乎所有高维计算的应用程序迟早都会面临维数灾难。本研究寻求算法来克服这个诅咒，其中的指导问题是：几何优化问题承认有效的算法与准确的近似？鉴于现代数据科学应用规模的大幅增长，需要新的算法技术来推动进一步的发展。该项目旨在为可以有效解决的问题开发核心算法原则，并确定不允许有效算法的问题的基本限制。 该教育计划包括通过家庭作业模块增强课程教学法，通过“发现”过程指导学生理解困难的概念。该项目还包括指导研究生和博士后研究员，并通过LatinX in AI（LXAI）组织扩大参与。这个项目的进展沿着三个关键的算法方向，其中每一个突出了一个更广泛的主题，在几何优化，还没有很好地理解。 这些是（1）处理全局约束（例如，在计算最佳运输时）;（2）优化对象与成本（如在某些层次聚类问题中）;以及（3）规避硬度结果（如在最接近对问题中）。 每个挑战都有一套基础问题、知识和算法原则，本项目将解决这些问题。 研究计划背后的指导原则是降维和局部性（这些原则一起使用降维来增强最近邻搜索）。 在理论进步的推动下，该项目还将开发大规模几何优化的实际实施和基准工具，以邀请理论之外的创新。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。