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.