TRIPODS+X: RES: Collaborative Research: Scaling Up Descriptive Epidemiology and Metabolic Network Models via Faster Sampling

从具有多个属性的空间中按给定分布抽样是计算机科学中的一个基本问题。在过去的二十年里，抽样的实际应用在统计、网络、生物学、差异隐私以及最引人注目的机器学习等领域得到了迅速发展。抽样用于评估模型，作为优化的子程序，更广泛地用于探索大型复杂空间。在这些实际设置中，采样的时间复杂性是一个严重的限制；已知的方法通常需要将采样限制在非常小的实例中，或者求助于未经证实的启发式或过度限制的假设。这个项目将开发一个抽样工具包，并在真实数据集上对其进行评估-一个大规模的高维工具包，用于抽样平滑和非平稳分布，以及一套可以通过获取样本来计算或估计的函数。它将与健康度量学和系统生物学领域的专家合作开发。该项目的总体目标是产生一个通用的、开源的、可公开访问的软件，用于采样具有数百万个变量的非光滑对数凹分布。实现这些目标需要克服理论和实施方面的复杂挑战。新算法的灵感将来自于研究人员在凸优化、高维几何和随机化线性代数方面的专业知识，特别是他们在线性规划和体积计算方面的突破。在健康指标和系统生物学这两个目标应用领域，调查人员都与专家合作，开发并部署了当前最先进的软件工具。从这些经验中，他们准备在这些领域开发通用工具和进行数据驱动的发现。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Sampling from a given distribution from a space with many attributes is a fundamental problem in computer science. Over the past two decades, practical applications of sampling have proliferated in areas such as statistics, networking, biology, differential privacy, and, most notably, machine learning. Sampling is used to evaluate models, as a subroutine for optimization, and more generally for exploring large complex spaces. In these practical settings, the time complexity of sampling is a severe limitation; known methods often require either restricting sampling to very small instances or resorting to unproven heuristics or overly restrictive assumptions. This project will develop a toolkit for sampling and evaluate it on real data sets --- a large-scale, high-dimensional toolkit for sampling smooth and non-smooth distributions, and a suite of functions that can be computed or estimated using access to samples. It will be developed working together with domain experts in health metrics and systems biology.The overall goal of the project is to produce a general-purpose, open-source, and publicly accessible software for sampling non-smooth log-concave distributions with millions of variables. Achieving these goals requires overcoming complex challenges in both theory and implementation. The new algorithms will be inspired by the investigators' expertise in convex optimization, high dimensional geometry, and randomized linear algebra, especially their breakthroughs in linear programming and volume computation. In both target application domains, health metrics and systems biology, the investigators have worked with experts to develop the current state-of-the-art software tools and deployed them. Drawing from this experience, they are poised to both develop general tools and make data-driven discoveries in these domains.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.