Computation meets Statistics: Trade-offs and fundamental limits for large data sets
Speaker: Alekh Agarwal , UC Berkeley
Date: April 2 2012
Time: 4:00PM to 5:00PM
Location: 32-G449
Host: Tommi Jaakkola and Greg Wornell, EECS
Contact: Francis Doughty, 253-4602, doughty@mit.edu
The past decade has seen the emergence of datasets of an
unprecedented scale, with both large sample sizes and dimensionality.
Massive data sets arise in various domains, among them computer
vision, natural language processing, computational biology, social
networks analysis and recommendation systems, to name a few. In many
such problems, the bottleneck is not just the number of data samples,
but also the computational resources available to process the data.
Thus, a fundamental goal in these problems is to characterize how
estimation error behaves as a function of the sample size, number of
parameters, and the computational budget available.
In this talk, I present two research threads that provide
complementary lines of attack on this broader research agenda: lower
bounds for statistical estimation with computational constraints, and
(ii) interplay between statistical and computational complexities in
structured high-dimensional estimation. The first characterizes
fundamental limits in a uniform sense over all methods, whereas the
latter shows how we can beat worst case complexity estimates of the
computational problem by exploiting the statistical structure.
[Joint work with Pradeep Ravikumar, Sahand Neghaban, Peter Bartlett
and Martin Wainwright ]
Bio: Alekh Agarwal is a fifth year PhD student at UC Berkeley, jointly
advised by Peter Bartlett and Martin Wainwright. Alekh has received
PhD fellowships from Microsoft Research and Google. His main research
interests are in the areas of machine learning, convex optimization,
high-dimensional statistics, distributed machine learning and
understanding the computational trade-offs in machine learning
problems.
See other events that are part of CS Special Seminar Series 2011/2012
See other events happening in April 2012
