标题： 通过凸松弛的计算与统计权衡 显示英文标题

标题： Computational and Statistical Tradeoffs via Convex Relaxation

摘要： 在现代数据分析中，人们经常面临涉及海量数据集的统计推断问题。处理这些大规模数据集通常被视为一个重要的计算挑战。然而，如果数据是统计学家的主要资源，那么获取更多数据应被视为一种资产而非负担。本文描述了一种基于凸松弛的计算框架，当可以访问越来越多的数据时，该框架能够降低推断过程的计算复杂度。凸松弛技术已在理论计算机科学中得到广泛应用，因为它们为许多计算上难以解决的任务提供了可处理的近似算法。我们通过在一类去噪问题中提供具体的时间-数据权衡来展示这种方法在统计估计中的有效性。因此，凸松弛提供了一种原则性的方法，以利用更大数据集带来的统计增益来减少推断算法的运行时间。 显示英文摘要

摘要： In modern data analysis, one is frequently faced with statistical inference problems involving massive datasets. Processing such large datasets is usually viewed as a substantial computational challenge. However, if data are a statistician's main resource then access to more data should be viewed as an asset rather than as a burden. In this paper we describe a computational framework based on convex relaxation to reduce the computational complexity of an inference procedure when one has access to increasingly larger datasets. Convex relaxation techniques have been widely used in theoretical computer science as they give tractable approximation algorithms to many computationally intractable tasks. We demonstrate the efficacy of this methodology in statistical estimation in providing concrete time-data tradeoffs in a class of denoising problems. Thus, convex relaxation offers a principled approach to exploit the statistical gains from larger datasets to reduce the runtime of inference algorithms.