CAREER: Navigating the Curse of Dimensionality in Euclidean Optimization Problems

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

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. 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.