CAREER: Navigating the Curse of Dimensionality in Euclidean Optimization Problems

这个项目旨在研究“维度诅咒”，即许多几何数据的计算问题随着维度的增加而变得指数级困难的现象。深度学习方面的进展表明，高维几何和大规模计算可以模拟世界的许多方面。即使是乍一看似乎是非几何的概念，如单词的含义或绘画的艺术风格，也往往可以被高维空间的丰富所捕捉到。然而，这种丰富性也是为回答问题和执行任务而设计的算法难以处理的根源，几乎所有高维计算应用迟早都会面临维度的诅咒。这项研究寻求克服这一诅咒的算法，其中的指导性问题是：哪些几何优化问题允许具有准确近似的高效算法？鉴于现代数据科学应用规模的大幅增长，需要新的算法技术来推动进一步的发展。该项目旨在为可以有效解决的问题开发核心算法原理，并确定不允许使用有效算法的问题的根本限制。教育计划包括通过家庭作业模块加强课程教育学，这些模块引导学生通过一个“发现”的过程来解决困难的概念。该项目还包括指导研究生和博士后研究员，并通过拉丁美洲人在人工智能(LXAI)组织扩大参与。这个项目沿着三个关键的算法方向前进，每个方向都突出了几何优化中一个尚未被很好理解的更广泛的主题。它们是(1)处理全局约束(例如，在计算最优运输时)；(2)针对对象与成本进行优化(如在某些层级群集问题中)；以及(3)规避硬度结果(如在最接近的配对问题中)。每个挑战都伴随着它的一套基本问题、猜想和算法原则，本项目将解决这些问题。研究计划背后的指导原则是降维和局部性(这些原则结合在一起，使用降维来增强最近邻搜索)。在理论进步的推动下，该项目还将为大规模几何优化开发实用的实施和基准工具，作为一种鼓励超越理论的创新的方式。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.