CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20130603-131602451

[img]
Preview
PDF - Published Version
See Usage Policy.

727kB
[img]
Preview
PDF - Supplemental Material
See Usage Policy.

71kB
[img] PDF - Submitted Version
See Usage Policy.

346kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20130603-131602451

Abstract

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
https://doi.org/10.1073/pnas.1302293110 DOIArticle
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3612621/PubMed CentralArticle
https://arxiv.org/abs/1211.1073arXivDiscussion 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.
Funders:
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
DOI:10.1073/pnas.1302293110
Record Number:CaltechAUTHORS:20130603-131602451
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20130603-131602451
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:38759
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:04 Jun 2013 20:40
Last Modified:09 Nov 2021 23:39

Repository Staff Only: item control page