Statistical Estimation in Resource-Constrained Environments: Computation, Communication and Privacy

过去十年见证了科学和工程领域数据集的规模和丰富性的爆炸式增长。各种各样的应用领域导致了大规模的数据集。例子包括社交网络如Facebook，在线推荐系统如Amazon和Netflix，神经科学数据包括fMRI， EEG和脑机接口，图像/视频处理包括人脸识别，监控和安全。所有这些领域都需要有效的统计推断方法，即从数据中得出可操作结论的方法。统计学中的经典方法是研究推理算法而不考虑其计算和存储要求；这种方法导致许多方法根本无法实现大规模问题。本研究的目标是开发一个原则性框架，用于描述计算和存储约束下统计估计的基本限制。这种观点的转变将导致在资源有限的环境中开发新的计算效率高的统计估计方法。虽然最小最大风险的概念表征了统计估计的基本限制，但它是基于对数据的所有可测量函数取最小值，从而允许具有指数计算复杂性的估计器，需要令人望而却步的存储量，和/或泄露敏感数据。本提案的目标是研究基于限制可能估计量类别的统计极大极小的各种约束形式。提议的工作本质上是跨学科的，结合了数理统计、信息论、优化理论和计算复杂性的思想。第一个研究重点是计算成本和统计准确性之间的权衡。主要目标是理解在经典的极大极小风险和在多项式时间内运行的算法可实现的最低风险之间何时存在差距。具体的模型类包括高维形式的稀疏回归、稀疏主成分分析和神经网络中的分类问题。第二个研究重点是分布式环境下的估计。许多数据集是如此之大，以至于它们不能存储在一个单一的中心位置，而必须分成许多部分，并存储在单独的机器上，这些机器只能交流相对较少的信息。因此，一个重要的问题是描述分布式实现所需的最小通信量，以匹配集中式估计器的性能。

The past decade has witnessed an explosion in the scale and richness of data sets that arise in both science and engineering. A wide variety of application areas have lead to large-scale data sets. Examples include social networks such as Facebook, on-line recommender systems such as Amazon and Netflix, neuroscience data including fMRI, EEG, and brain-machine interfaces, and image/video processing which includes face recognition, surveillance, and security. All of these areas require effective methods for statistical inference---that is, methods that lead to actionable conclusions from the data. The classical approach in statistics is to study inference algorithms without consideration of their computational and storage requirements; this approach leads to many methods that simply cannot be implemented for large-scale problems. The goal of this research is to develop a principled framework for characterizing the fundamental limits of statistical estimation under computational and storage constraints. This shift in perspective will lead to the development of new and computationally efficient methods for statistical estimation in resource-constrained environments.While the notion of minimax risk characterizes the fundamental limits of statistical estimation, it is based on taking an infimum over all measurable functions of data, thereby allowing for estimators that have exponential computational complexity, require prohibitive amounts of storage, and/or reveal sensitive data. The goal of this proposal is to study various constrained forms of statistical minimax based on limiting the class of possible estimators. The proposed work is interdisciplinary in nature, combining ideas from mathematical statistics, information theory, optimization theory, and computational complexity. The first research thrust concerns the tradeoffs between computational costs and statistical accuracy. The main goal is to understand when there are gaps between the classical minimax risk, and the lowest risk achievable by algorithms that run in polynomial-time. Specific model classes of interest include high-dimensional forms of sparse regression, sparse principal component analysis, and classification problems in neural networks. The second research thrust focuses on estimation in distributed settings. Many data sets are so large so that they cannot be stored at a single central location, but instead must be split into many pieces, and stored on separate machines that can communicate only relatively small amounts of information. Thus, an important problem is to characterize the minimal amount of communication needed for a distributed implementation to match the performance of the centralized estimator.