A Caltech Library Service

Computational and statistical tradeoffs via convex relaxation

Chandrasekaran, Venkat and Jordan, Michael I. (2013) Computational and statistical tradeoffs via convex relaxation. Proceedings of the National Academy of Sciences of the United States of America, 110 (13). E1181-E1190. ISSN 0027-8424. PMCID PMC3612621. doi:10.1073/pnas.1302293110.

PDF - Published Version
See Usage Policy.

PDF - Supplemental Material
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Modern massive datasets create a fundamental problem at the intersection of the computational and statistical sciences: how to provide guarantees on the quality of statistical inference given bounds on computational resources, such as time or space. Our approach to this problem is to define a notion of “algorithmic weakening,” in which a hierarchy of algorithms is ordered by both computational efficiency and statistical efficiency, allowing the growing strength of the data at scale to be traded off against the need for sophisticated processing. We illustrate this approach in the setting of denoising problems, using convex relaxation as the core inferential tool. Hierarchies of convex relaxations have been widely used in theoretical computer science to yield tractable approximation algorithms to many computationally intractable tasks. In the current paper, we show how to endow such hierarchies with a statistical characterization and thereby obtain concrete tradeoffs relating algorithmic runtime to amount of data.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle CentralArticle Paper
Additional Information:© 2013 National Academy of Sciences. Freely available online through the PNAS open access option. Contributed by Michael I. Jordan, February 5, 2013 (sent for review November 27, 2012). Published online before print March 11, 2013. We thank Pablo Parrilo, Benjamin Recht, and Parikshit Shah for many insightful conversations. We also thank Alekh Agarwal, Peter Bühlmann, Emmanuel Candès, Robert Nowak, James Saunderson, Leonard Schulman, and Martin Wainwright for helpful questions and discussions. This material is based on work supported, in part, by the US Army Research Laboratory and the US Army Research Office under Contract/Grant W911NF-11-1-0391. Author contributions: V.C. and M.I.J. designed research, performed research, and wrote the paper.
Funding AgencyGrant Number
Army Research LaboratoryUNSPECIFIED
Army Research Office (ARO)W911NF-11-1-0391
Subject Keywords:convex geometry; convex optimization; high-dimensional statistics
Issue or Number:13
PubMed Central ID:PMC3612621
Record Number:CaltechAUTHORS:20130603-131602451
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:38759
Deposited On:04 Jun 2013 20:40
Last Modified:09 Nov 2021 23:39

Repository Staff Only: item control page