Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 26, 2013 | Submitted + Published + Supplemental Material
Journal Article Open

Computational and statistical tradeoffs via convex relaxation


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.

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.

Attached Files

Published - PNAS-2013-Chandrasekaran-E1181-90.pdf

Submitted - 1211.1073.pdf

Supplemental Material - sapp.pdf


Files (1.1 MB)
Name Size Download all
727.9 kB Preview Download
346.9 kB Preview Download
71.6 kB Preview Download

Additional details

August 22, 2023
October 23, 2023