AF: Small: High-dimensional geometry and probability for efficient inference

AF：小：高维几何和概率以实现高效推理

• 批准号: 2006994
• 负责人: Luis Rademacher
• 金额: $ 45万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2024-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006994&HistoricalAwards=false
• 关键词: AF; Small; dimensional; geometry; probability

A fundamental challenge of this time is inference, that is the extraction of information from data. A particular challenge from the algorithmic perspective is the curse of dimensionality. This involves the exponential explosion of computational cost as the number of features of the data grows. The project will advance the understanding of data with many features and provide new tools for data summarization. It has a high potential of leading to the development of new practical algorithms to extract information from data. The main educational outcome of the project will be to train PhD students in theoretical computer science and to provide research experience and mentoring to undergraduate students. The project will enrich the experience of PhD students by funding their attendance to prestigious workshops on the foundations of data science and other aspects of theoretical computer science.The project will design new tools for efficient inference and solidify understanding of existing tools. The focus will be on tensor methods, deconvolution and convex optimization. The underlying theme is the use of ideas from high-dimensional probability, and discrete and convex geometry. The rationale for these choices is twofold. Firstly, the research team is highly qualified in those fields. Secondly, those foundational fields provide some of the most powerful tools available to understand high-dimensional data. Within the broader topics of the project, this project will focus on (1) Frank-Wolfe methods in optimization, (2) blind and non-blind deconvolution and the interplay with tensor methods and parameter estimation for Gaussian mixture models, and (3) geometric tools to describe and summarize the shape of data. The project will provide insight into well-recognized challenges. While the questions are challenging, in recent years there has been steady progress on them, such as new insights into tensor methods. A specific intellectual opportunity is the identification of the right tools in high-dimensional probability and discrete and convex geometry that provide insight into the design of new algorithms for inference and data analysis. The proposed work on the foundations of data science and optimization has connections with random polytopes, random matrices, high-dimensional probability and discrete and convex geometry. The proposed work is expected to provide more instances of "cross-pollination," where theoretical tools can aid the design of new algorithms and the algorithmic approach provides new questions and motivations to theoretical fields.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.

这个时代的一个根本挑战是推理，即从数据中提取信息。从算法的角度来看，一个特别的挑战是维度的诅咒。这涉及到随着数据特征数量的增长，计算成本呈指数级爆炸式增长。该项目将促进对具有许多特征的数据的理解，并为数据汇总提供新的工具。它有很高的潜力引导开发新的实用算法来从数据中提取信息。该项目的主要教育成果将是培训博士生理论计算机科学，并为本科生提供研究经验和指导。该项目将通过资助博士生参加关于数据科学基础和其他理论计算机科学方面的著名研讨会来丰富他们的经验。该项目将设计新的工具来进行有效的推理并巩固对现有工具的理解。重点将放在张量方法、反卷积和凸优化上。基本主题是使用高维概率、离散几何和凸几何中的思想。这些选择的理由有两个。首先，研究团队在这些领域具有很高的素质。其次，这些基础字段提供了一些可用于理解高维数据的最强大的工具。在项目更广泛的主题中，本项目将重点关注(1)最优化中的Frank-Wolfe方法，(2)盲和非盲反卷积以及与张量方法和高斯混合模型参数估计的相互作用，以及(3)描述和总结数据形状的几何工具。该项目将提供对公认挑战的洞察。虽然这些问题具有挑战性，但近年来在这些问题上取得了稳步进展，例如对张量方法的新见解。一个特殊的智力机会是在高维概率和离散几何和凸几何中识别正确的工具，这些工具提供了对推理和数据分析的新算法设计的洞察。拟议中的数据科学和优化基础工作与随机多面体、随机矩阵、高维概率以及离散和凸几何有关。这项拟议的工作预计将提供更多的“交叉授粉”实例，其中理论工具可以帮助设计新的算法，而算法方法为理论领域提供新的问题和动机。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Improved Bounds for the Expected Number of k-Sets

改进 k 集预期数量的界限

• DOI: 10.1007/s00454-022-00469-7
• 发表时间: 2023
• 期刊: Discrete & Computational Geometry
• 影响因子: 0.8
• 作者: Leroux, Brett;Rademacher, Luis
• 通讯作者: Rademacher, Luis

The smoothed complexity of Frank–Wolfe methods via conditioning of random matrices and polytopes

通过随机矩阵和多面体调节的 Frank-Wolfe 方法的平滑复杂度

• DOI: 10.4171/msl/35
• 发表时间: 2022
• 期刊: Mathematical Statistics and Learning
• 作者: Rademacher, Luis;Shu, Chang
• 通讯作者: Shu, Chang

Algebraic k-Sets and Generally Neighborly Embeddings

代数 k 集和广义邻域嵌入

• DOI: 10.1007/s00454-021-00340-1
• 发表时间: 2022
• 期刊: Discrete & Computational Geometry
• 影响因子: 0.8
• 作者: Leroux, Brett;Rademacher, Luis
• 通讯作者: Rademacher, Luis