CAREER: Navigating the Curse of Dimensionality in Euclidean Optimization Problems

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

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.