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 的法定使命，并通过使用基金会的评估进行评估，认为值得支持。智力价值和更广泛的影响审查标准。