Computational Tradeoffs in Statistical Estimation

• Activity Number: 2
• Type: Invited
• Date/Time: Sunday, August 9, 2015 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): John Lafferty*
• Companies: The University of Chicago
• Keywords: nonparametric estimation ; computational efficiency ; minimax theory ; constrained statistics

Abstract

In massive data analysis, statistical estimation needs to be carried out with close attention to computational resources -- compute cycles, communication bandwidth and storage capacity. Yet relatively little is known about the fundamental tradeoffs between statistical and computational efficiency. This talk will summarize previous results is this direction, and present recent work that revisits classical linear and nonparametric estimation theory from a computational perspective. In particular, we formulate an extension to Pinsker's theorem in the setting of rate distortion theory, and present algorithms for trading off estimation accuracy for computational speed in linear and nonparametric regression. Finally, we sketch some potentially promising future research directions in computation-constrained statistics.