Complexity of High-Dimensional Statistical Models: An Information-Based Approach

大数据带来了更大的目标-许多现代统计应用不仅涉及可能提供新见解的大型数据集，而且还需要破译大量变量之间高度复杂的关系，这些变量通常具有非常复杂和高维的功能。随着获取的数据越来越多，这些功能不可避免地变得越来越复杂。通常，这些应用程序面临的最根本的挑战是如何量化这些任务的复杂性，并以有效的方式从数据中学习这些功能，包括统计和计算。尽管近年来取得了令人印象深刻的进展，目前实现这一目标的方法是有限的离散性质的经典概念的计算复杂性，并不适合统计问题是连续的。该项目旨在开发一种基于信息的方法，更好地兼顾统计和计算效率。这种新的复杂性框架，预计将提供洞察统计和计算效率之间的潜在权衡，并揭示实验设计在减轻计算负担的作用。该项目通过参与研究为研究生提供培训。传统的非参数技术完全基于光滑性，已知遭受所谓的“维数灾难”。“但在许多科学和工程应用中，潜在的高维对象可能具有额外的结构，如果适当地考虑，本项目旨在开发一个连贯的框架来量化高维模型的复杂性，该框架适当地考虑了统计准确性和计算成本，并有助于更好地理解这些额外的结构。该项目将使用复杂性的概念来研究几个常见但非常困难的高维非参数回归问题：一个仅基于平滑性，另一个基于平滑性和稀疏性，最后一个基于低秩张量。该练习旨在揭示这些问题的统计和计算方面之间的有趣关系，并导致新的和最佳的抽样和估计策略的发展。该研究将在更一般的统计背景下开发新的复杂性框架，并研究其在表征统计和计算最优推理方案中的作用。这将通过开发新的统计方法和计算算法，对其性能和基本限制进行理论研究，以及开发相关的数学工具和计算软件来实现。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

With big data come bigger goals – many modern statistical applications not only involve large datasets that may offer new insights but also require deciphering highly intricate relationships among a large number of variables, often characterized by very complex and high-dimensional functions. As more data are acquired, these functions inevitably become more complex. Oftentimes the most fundamental challenge for these applications is how to quantify the complexity of such tasks and learn these functions from data in an efficient way, both statistically and computationally. Despite impressive progress made in recent years, the current approach towards this goal is limited by the discrete nature of the classical notion of computational complexity and is not suitable for statistical problems that are continuous. This project aims to develop an information-based approach that better accounts for both statistical and computational efficiencies. This new framework of complexity is expected to offer insights into the potential trade-off between statistical and computational efficiencies and to reveal the role of experimental design in alleviating computational burden. The project provides training for graduate students through involvement in the research.Traditional nonparametric techniques based solely on smoothness are known to suffer from the so-called "curse of dimensionality." But in many scientific and engineering applications, the underlying high-dimensional object may have additional structures which, if appropriately accounted for, could help lift this barrier and allow for efficient methods to handle it. This project aims to develop a coherent framework to quantify the complexity of high dimensional models that appropriately accounts for both statistical accuracy and computational cost and helps better understand the role of these additional structures. The project will use this notion of complexity to examine several common yet notoriously difficult high-dimensional nonparametric regression problems: one based solely on smoothness, another based on smoothness and sparsity, and finally, one based on low-rank tensors. The exercise is designed to reveal interesting relationships between statistical and computational aspects of these problems and lead to the development of novel and optimal sampling and estimation strategies. The research will develop the new framework of complexity in more general statistical contexts as well and investigate its role in characterizing statistically and computationally optimal inference schemes. This will be achieved by developing new statistical methods and computational algorithms, theoretical study of their performance and fundamental limits, and the development of related mathematical tools and computational software.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.