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

Noon Lunch chalk talk for trainees: 330 Gross Hall Seminar 3:30-4:30pm, 2231 French Family Science CenterReception following talk, 330 Gross HallAbstract: In massive data analysis, statistical estimation needs to be carriedout with close attention to computational resources -- compute cycles,communication bandwidth and storage capacity. Yet little is presentlyknown about the fundamental tradeoffs between statistical andcomputational efficiency. We present recent work that revisitsclassical linear and nonparametric estimation from a computationalperspective. In particular, we formulate an extension to minimaxtheory in terms of rate distortion theory, and present algorithms fortrading off estimation accuracy for computational speed in linear andnonparametric regression. We also present a weakening of the worstcase analysis of algorithms motivated from statistical theory, andrevisit stochastic convex optimization in terms of this framework,deriving new computational lower bounds. Joint work with YuanchengZhu and Dinah Shender of the University of Chicago.