Speaker: Veeranjaneyulu Sadhanala

**Abstract:**
Given a statistical estimation problem where regularization is
performed according to the structure of a large, dense graph G,
we consider fitting the statistical estimate using a
sparsified surrogate graph \tilde{G}, which shares the
vertices of G but has far fewer edges, and is thus more tractable
to work with computationally.
We examine three types of sparsification: spectral
sparsification, which can be seen as the result of sampling edges from
the graph with probabilities proportional to their effective
resistances, and two simpler sparsifiers, which sample edges
uniformly from the graph, either globally or locally. We provide
strong theoretical and experimental results, demonstrating that
sparsification before estimation gives statistically sensible
solutions, with potential computational savings.