Geometric Methods in Data Analysis

基于将数据点视为高维空间元素的数据的几何视图，在计算机科学和统计学中有着悠久的传统。例如，在机器学习中，通常将数据表示为点的集合，每个点对应于一个特定的示例，例如标记的图像。数据点的个别特征，例如图像的像素，给出了数据点在坐标系中的坐标。然后，许多标准的机器学习任务可以用几何形式表示。例如，根据内容对图像进行分类可以表述为在图像的高维空间中找到一个合适的几何形状分区。另一个例子，寻找相似的图像对应于寻找在适当的距离度量中接近的点。这样的公式允许利用高维几何的数学见解来解决具有挑战性的数据分析任务。尽管数据的几何视图有着悠久的传统，但对于许多基本的数据分析任务，我们仍然缺乏对任务的底层几何如何与其统计和计算硬度相互作用的完整理解。与此相关的是，我们通常不知道解决这些任务的算法，也不知道如何最佳地适应数据的几何形状。该项目的长期目标是发展数据分析中心算法任务的几何理论。特别是，该理论应该预测每个任务的统计和计算复杂性，例如解决它所需的数据量，以及最优算法的效率。该理论还应该为设计简单而有效的算法提供原则，以最佳地适应数据的底层几何。算法还应该是动态的，即能够适应数据的变化或正在解决的问题。该项目感兴趣的数据分析的主要领域是私人统计数据分析、高维搜索和实验设计。使用几何工具攻击这些领域的短期目标是：*在私人数据分析中：设计最优和有效的算法来回答计数查询，以及随机优化问题，如分类，逻辑和最小二乘回归；设计具有竞争力的算法，实现数据的交互式分析；描述在私有数据分析的分布式模型中允许交互时可以更有效地解决哪些任务。*在高维搜索中：描述存在基于随机空间分区的高效近邻搜索数据结构的度量，以及更一般的计算模型（如决策树）中的数据结构。*在实验设计中：开发有效的算法，在组合约束下近似计算最优实验设计。

A geometric view of data, based on treating data points as elements of a high dimensional space, has long traditions in computer science and statistics. For example, in machine learning, it is common to represent data as a collection of points, each point corresponding to a particular example, such as a labeled image. The individual features of the data points, e.g. the pixels of the image, give the coordinates of the data point in a coordinate system. Many standard machine learning tasks can then be formulated geometrically. For example, classifying images according to their content can be formulated as finding an appropriate partition of this high dimensional space of images into geometric shapes. For another example, finding similar images corresponds to finding points that are close in an appropriate distance metric. Such formulations allow leveraging mathematical insights from high-dimensional geometry to solve challenging data analysis tasks. Despite the long traditions of a geometric view of data, for many fundamental data analysis tasks we still lack a complete understanding of how the underlying geometry of the task interacts with its statistical and computational hardness. Relatedly, we often do not know algorithms that solve these tasks and adapt optimally to the geometry of the data. The long-term objective of this project is develop a geometric theory of central algorithmic tasks in data analysis. In particular, the theory should predict the statistical and computational complexity of each task, such as the amount of data required to solve it, and the efficiency of an optimal algorithm for it. The theory should also provide principles for the design of simple, and efficient algorithms that optimally adapt to the underlying geometry of the data. The algorithms should also be dynamic, in the sense of being able to adapt to changes in the data or to the problem being solved. The main areas of data analysis that are of interest for the project are private statistical data analysis, high-dimensional search, and experimental design. The short term objectives in each of these areas that will be attacked using geometric tools are: * In private data analysis: design optimal and efficient algorithms for answering counting queries, and for stochastic optimization problems like classification, logistic, and least-squares regression; design competitive algorithms that enable interactive analysis of the data; characterize what tasks can be solved more efficiently when interaction is allowed in distributed models of private data analysis. * In high dimensional search: characterize the metrics for which there exist efficient near neighbour search data structures based on randomized space partitions, as well as data structures in the more general computational models, such as decision trees. * In experimental design:  develop efficient algorithms that approximately compute optimal experimental designs under combinatorial constraints.