Exchanging Bips for Flops and Bits: Computational Tradeoffs in Statistical Learning

Nov 18

Monday, November 18, 2013

3:30 pm - 4:30 pm
French Family Science Center 2231


John Lafferty

Noon Lunch chalk talk for trainees: 330 Gross Hall Seminar 3:30-4:30pm, 2231 French Family Science Center Reception following talk, 330 Gross Hall 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 little is presently known about the fundamental tradeoffs between statistical and computational efficiency. We present recent work that revisits classical linear and nonparametric estimation from a computational perspective. In particular, we formulate an extension to minimax theory in terms of rate distortion theory, and present algorithms for trading off estimation accuracy for computational speed in linear and nonparametric regression. We also present a weakening of the worst case analysis of algorithms motivated from statistical theory, and revisit stochastic convex optimization in terms of this framework, deriving new computational lower bounds. Joint work with Yuancheng Zhu and Dinah Shender of the University of Chicago.