Back to Departmental Colloquium: Fall 2015
Departmental Colloquium
Date: Thursday, Nov 5, 2015
Time: 4:00PM
Location: LCB 219
Rachel Ward
University of Texas at Austin
Title |
Importance sampling in large-scale machine learning problems: why it works and how it can help |
Abstract |
A recent trend in signal processing and machine learning research is that exact reconstruction is achievable from highly subsampled data by passing to nonlinear, sparsity-inducing, reconstruction methods such as l1 minimization. Such guarantees often require strong structural conditions on the data in addition to sparsity, such as incoherence, which render the theory unusable on problems of practical importance. Here, we show that many of these strong assumptions are tied to i.i.d uniform sampling, and can be dropped by allowing weighted, or importance sampling. First, we explain why importance sampling works in this context: it aims to make the inverse problem as well-conditioned as possible given a fixed sample budget. We then discuss several problem domains where importance sampling strategies can be derived explicitly, and outperform state-of-the-art sampling strategies used in practice: medical imaging, collaborative filtering, uncertainty quantification, and stochastic gradient methods. Along the way, we derive results at the intersection of applied harmonic analysis and random matrix theory that are of independent interest. |
Probability
Computational Mathematics