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

标题： Computational and Sample 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.