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

资源受限环境中的统计估计：计算、通信和隐私

• 批准号: 1612948
• 负责人: Martin Wainwright
• 金额: $ 30万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1612948&HistoricalAwards=false
• 关键词: Statistical; Estimation; Resource; Constrained; Environments

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.

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