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.