AF: Small: Approximation Algorithms for Learning Metric Spaces

在科学和工程的几个分支中，对大型和复杂数据集的分析是一项日益重要的任务。在许多应用场景中，数据由一组被赋予某些信息的对象组成，这些信息量化了某些对的相似或不同。这些输入的例子包括统计分布、社交网络中的用户偏好、DNA序列等。将这样的数据集解释为公制空间是一种自然的方式。也就是说，每个对象被视为一个点，并且两个对象之间的差异性通过它们的距离来编码。这一数据分析框架的成功应用需要找到一个忠实地编码基本事实的距离函数。该项目寻求开发新的算法来计算数据集的这种忠实的度量表示。潜在的研究问题导致了计算几何、算法设计和机器学习领域之间的新联系。该项目的目的是在这些科学界之间传递思想，并在实践中开发新的数据分析方法。该项目将是调查员课程开发、教学、教育和外联活动的一部分。该项目试图研究的主要研究问题将成为本科生和研究生培养的基础。研究人员致力于处理少数族裔和代表性不足的群体。这种对数据集的计量解释在实践中取得了成功，并产生了过多的算法方法和思想，如聚类、降维、最近邻搜索等。度量学习的领域主要涉及发现与给定观测集一致的潜在度量空间的方法。具体地说，学习距离函数的问题被描述为优化问题，其中目标函数量化了解满足输入约束的程度。在许多关于度量学习的著作中，一个共同的主线是使用计算几何和度量嵌入理论中的方法和思想。在过去的几十年里，这些想法也一直是理论计算机科学界的研究主题。然而，度量学习中有几个研究得很好的问题在算法和计算几何界并没有得到太多关注。此外，还有许多在算法社区内开发的度量嵌入工具和技术，尚未在度量学习的上下文中使用。该项目旨在通过从计算几何和近似算法的角度对算法度量学习问题进行系统研究来弥合这一差距。这项工作的主要目标是将算法工具转移到度量学习框架中，并为在实践中成功但目前缺乏可证明的保证的度量学习方法提供理论上的合理性。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The analysis of large and complicated data sets is a task of increasing importance in several brunches of science and engineering. In many application scenarios, the data consists of a set of objects endowed with some information that quantifies similarity or dissimilarity of certain pairs. Examples of such inputs include statistical distributions, user preferences in social networks, DNA sequences, and so on. A natural way to interpret such data sets is as metric spaces. That is, each object is treated as a point, and the dissimilarity between two objects is encoded by their distance. The successful application of this data-analytic framework requires finding a distance function that faithfully encodes the ground truth. The project seeks to develop new algorithms for computing such faithful metrical representations of data sets. The underlying research problems lead to new connections between the areas of computational geometry, algorithm design, and machine learning. The project aims at transferring ideas between these scientific communities, and developing new methods for data analysis in practice. The project will be part of the investigator's curriculum development, teaching, and educational and outreach activities. The main research problems that the project seeks to study will form the basis for the training of both undergraduate and graduate students. The investigator is committed to working with minorities and underrepresented groups.This metrical interpretation of data sets has been successful in practice and has lead to a plethora of algorithmic methods and ideas, such as clustering, dimensionality reduction, nearest-neighbor search, and so on. The area of metric learning is concerned mainly with methods for discovering an underlying metric space that agrees with a given set of observations. Specifically, the problem of learning the distance function is cast as an optimization problem, where the objective function quantifies the extend to which the solution satisfies the input constraints. A common thread in many works on metric learning is the use of methods and ideas from computational geometry and the theory of metric embeddings. Over the past few decades, these ideas have also been the subject of study within the theoretical computer science community. However, there are several well-studied problems in metric learning that have not received much attention in the algorithms and computational geometry communities. Moreover, there are many metric embedding tools and techniques, that where developed within the algorithms community, that have not yet been used in the context of metric learning. The project aims at bridging this gap by a systematic study of algorithmic metric learning problems from the point of view of computational geometry and approximation algorithms. The major goals of this effort are transferring algorithmic tools to the metric learning framework, as well as providing theoretical justification for metric learning methods that are successful in practice but currently lack provable guarantees.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.